Actual source code: sbaijfact2.c

      1: /*
      2:     Factorization code for SBAIJ format.
      3: */

      5: #include <../src/mat/impls/sbaij/seq/sbaij.h>
      6: #include <../src/mat/impls/baij/seq/baij.h>
      7: #include <petsc/private/kernels/blockinvert.h>

      9: PetscErrorCode MatSolve_SeqSBAIJ_N_inplace(Mat A, Vec bb, Vec xx)
     10: {
     11:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
     12:   IS                 isrow = a->row;
     13:   PetscInt           mbs = a->mbs, *ai = a->i, *aj = a->j;
     14:   const PetscInt    *r;
     15:   PetscInt           nz, *vj, k, idx, k1;
     16:   PetscInt           bs = A->rmap->bs, bs2 = a->bs2;
     17:   const MatScalar   *aa = a->a, *v, *diag;
     18:   PetscScalar       *x, *xk, *xj, *xk_tmp, *t;
     19:   const PetscScalar *b;

     21:   PetscFunctionBegin;
     22:   PetscCheck(bs > 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Expected bs %" PetscInt_FMT " > 0", bs);
     23:   PetscCall(VecGetArrayRead(bb, &b));
     24:   PetscCall(VecGetArray(xx, &x));
     25:   t = a->solve_work;
     26:   PetscCall(ISGetIndices(isrow, &r));
     27:   PetscCall(PetscMalloc1(bs, &xk_tmp));

     29:   /* solve U^T * D * y = b by forward substitution */
     30:   xk = t;
     31:   for (k = 0; k < mbs; k++) { /* t <- perm(b) */
     32:     idx = bs * r[k];
     33:     for (k1 = 0; k1 < bs; k1++) *xk++ = b[idx + k1];
     34:   }
     35:   for (k = 0; k < mbs; k++) {
     36:     v  = aa + bs2 * ai[k];
     37:     xk = t + k * bs;                          /* Dk*xk = k-th block of x */
     38:     PetscCall(PetscArraycpy(xk_tmp, xk, bs)); /* xk_tmp <- xk */
     39:     nz = ai[k + 1] - ai[k];
     40:     vj = aj + ai[k];
     41:     xj = t + (*vj) * bs; /* *vj-th block of x, *vj>k */
     42:     while (nz--) {
     43:       /* x(:) += U(k,:)^T*(Dk*xk) */
     44:       PetscKernel_v_gets_v_plus_Atranspose_times_w(bs, xj, v, xk_tmp); /* xj <- xj + v^t * xk */
     45:       vj++;
     46:       xj = t + (*vj) * bs;
     47:       v += bs2;
     48:     }
     49:     /* xk = inv(Dk)*(Dk*xk) */
     50:     diag = aa + k * bs2;                                /* ptr to inv(Dk) */
     51:     PetscKernel_w_gets_A_times_v(bs, xk_tmp, diag, xk); /* xk <- diag * xk */
     52:   }

     54:   /* solve U*x = y by back substitution */
     55:   for (k = mbs - 1; k >= 0; k--) {
     56:     v  = aa + bs2 * ai[k];
     57:     xk = t + k * bs; /* xk */
     58:     nz = ai[k + 1] - ai[k];
     59:     vj = aj + ai[k];
     60:     xj = t + (*vj) * bs;
     61:     while (nz--) {
     62:       /* xk += U(k,:)*x(:) */
     63:       PetscKernel_v_gets_v_plus_A_times_w(bs, xk, v, xj); /* xk <- xk + v*xj */
     64:       vj++;
     65:       v += bs2;
     66:       xj = t + (*vj) * bs;
     67:     }
     68:     idx = bs * r[k];
     69:     for (k1 = 0; k1 < bs; k1++) x[idx + k1] = *xk++;
     70:   }

     72:   PetscCall(PetscFree(xk_tmp));
     73:   PetscCall(ISRestoreIndices(isrow, &r));
     74:   PetscCall(VecRestoreArrayRead(bb, &b));
     75:   PetscCall(VecRestoreArray(xx, &x));
     76:   PetscCall(PetscLogFlops(4.0 * bs2 * a->nz - (bs + 2.0 * bs2) * mbs));
     77:   PetscFunctionReturn(PETSC_SUCCESS);
     78: }

     80: PetscErrorCode MatForwardSolve_SeqSBAIJ_N_inplace(Mat A, Vec bb, Vec xx)
     81: {
     82:   PetscFunctionBegin;
     83:   SETERRQ(PETSC_COMM_SELF, PETSC_ERR_SUP, "not implemented yet");
     84: }

     86: PetscErrorCode MatBackwardSolve_SeqSBAIJ_N_inplace(Mat A, Vec bb, Vec xx)
     87: {
     88:   PetscFunctionBegin;
     89:   SETERRQ(PETSC_COMM_SELF, PETSC_ERR_SUP, "Not yet implemented");
     90: }

     92: static PetscErrorCode MatForwardSolve_SeqSBAIJ_N_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscInt bs, PetscScalar *x)
     93: {
     94:   PetscInt         nz, k;
     95:   const PetscInt  *vj, bs2 = bs * bs;
     96:   const MatScalar *v, *diag;
     97:   PetscScalar     *xk, *xj, *xk_tmp;

     99:   PetscFunctionBegin;
    100:   PetscCheck(bs > 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Expected bs %" PetscInt_FMT " > 0", bs);
    101:   PetscCall(PetscMalloc1(bs, &xk_tmp));
    102:   for (k = 0; k < mbs; k++) {
    103:     v  = aa + bs2 * ai[k];
    104:     xk = x + k * bs;                          /* Dk*xk = k-th block of x */
    105:     PetscCall(PetscArraycpy(xk_tmp, xk, bs)); /* xk_tmp <- xk */
    106:     nz = ai[k + 1] - ai[k];
    107:     vj = aj + ai[k];
    108:     xj = x + (size_t)(*vj) * bs; /* *vj-th block of x, *vj>k */
    109:     while (nz--) {
    110:       /* x(:) += U(k,:)^T*(Dk*xk) */
    111:       PetscKernel_v_gets_v_plus_Atranspose_times_w(bs, xj, v, xk_tmp); /* xj <- xj + v^t * xk */
    112:       vj++;
    113:       xj = x + (size_t)(*vj) * bs;
    114:       v += bs2;
    115:     }
    116:     /* xk = inv(Dk)*(Dk*xk) */
    117:     diag = aa + k * bs2;                                /* ptr to inv(Dk) */
    118:     PetscKernel_w_gets_A_times_v(bs, xk_tmp, diag, xk); /* xk <- diag * xk */
    119:   }
    120:   PetscCall(PetscFree(xk_tmp));
    121:   PetscFunctionReturn(PETSC_SUCCESS);
    122: }

    124: static PetscErrorCode MatBackwardSolve_SeqSBAIJ_N_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscInt bs, PetscScalar *x)
    125: {
    126:   PetscInt         nz, k;
    127:   const PetscInt  *vj, bs2 = bs * bs;
    128:   const MatScalar *v;
    129:   PetscScalar     *xk, *xj;

    131:   PetscFunctionBegin;
    132:   for (k = mbs - 1; k >= 0; k--) {
    133:     v  = aa + bs2 * ai[k];
    134:     xk = x + k * bs; /* xk */
    135:     nz = ai[k + 1] - ai[k];
    136:     vj = aj + ai[k];
    137:     xj = x + (size_t)(*vj) * bs;
    138:     while (nz--) {
    139:       /* xk += U(k,:)*x(:) */
    140:       PetscKernel_v_gets_v_plus_A_times_w(bs, xk, v, xj); /* xk <- xk + v*xj */
    141:       vj++;
    142:       v += bs2;
    143:       xj = x + (size_t)(*vj) * bs;
    144:     }
    145:   }
    146:   PetscFunctionReturn(PETSC_SUCCESS);
    147: }

    149: PetscErrorCode MatSolve_SeqSBAIJ_N_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    150: {
    151:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    152:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    153:   PetscInt           bs = A->rmap->bs;
    154:   const MatScalar   *aa = a->a;
    155:   PetscScalar       *x;
    156:   const PetscScalar *b;

    158:   PetscFunctionBegin;
    159:   PetscCall(VecGetArrayRead(bb, &b));
    160:   PetscCall(VecGetArray(xx, &x));

    162:   /* solve U^T * D * y = b by forward substitution */
    163:   PetscCall(PetscArraycpy(x, b, bs * mbs)); /* x <- b */
    164:   PetscCall(MatForwardSolve_SeqSBAIJ_N_NaturalOrdering(ai, aj, aa, mbs, bs, x));

    166:   /* solve U*x = y by back substitution */
    167:   PetscCall(MatBackwardSolve_SeqSBAIJ_N_NaturalOrdering(ai, aj, aa, mbs, bs, x));

    169:   PetscCall(VecRestoreArrayRead(bb, &b));
    170:   PetscCall(VecRestoreArray(xx, &x));
    171:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (bs + 2.0 * a->bs2) * mbs));
    172:   PetscFunctionReturn(PETSC_SUCCESS);
    173: }

    175: PetscErrorCode MatForwardSolve_SeqSBAIJ_N_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    176: {
    177:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    178:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    179:   PetscInt           bs = A->rmap->bs;
    180:   const MatScalar   *aa = a->a;
    181:   const PetscScalar *b;
    182:   PetscScalar       *x;

    184:   PetscFunctionBegin;
    185:   PetscCall(VecGetArrayRead(bb, &b));
    186:   PetscCall(VecGetArray(xx, &x));
    187:   PetscCall(PetscArraycpy(x, b, bs * mbs)); /* x <- b */
    188:   PetscCall(MatForwardSolve_SeqSBAIJ_N_NaturalOrdering(ai, aj, aa, mbs, bs, x));
    189:   PetscCall(VecRestoreArrayRead(bb, &b));
    190:   PetscCall(VecRestoreArray(xx, &x));
    191:   PetscCall(PetscLogFlops(2.0 * a->bs2 * a->nz - bs * mbs));
    192:   PetscFunctionReturn(PETSC_SUCCESS);
    193: }

    195: PetscErrorCode MatBackwardSolve_SeqSBAIJ_N_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    196: {
    197:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    198:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    199:   PetscInt           bs = A->rmap->bs;
    200:   const MatScalar   *aa = a->a;
    201:   const PetscScalar *b;
    202:   PetscScalar       *x;

    204:   PetscFunctionBegin;
    205:   PetscCall(VecGetArrayRead(bb, &b));
    206:   PetscCall(VecGetArray(xx, &x));
    207:   PetscCall(PetscArraycpy(x, b, bs * mbs));
    208:   PetscCall(MatBackwardSolve_SeqSBAIJ_N_NaturalOrdering(ai, aj, aa, mbs, bs, x));
    209:   PetscCall(VecRestoreArrayRead(bb, &b));
    210:   PetscCall(VecRestoreArray(xx, &x));
    211:   PetscCall(PetscLogFlops(2.0 * a->bs2 * (a->nz - mbs)));
    212:   PetscFunctionReturn(PETSC_SUCCESS);
    213: }

    215: PetscErrorCode MatSolve_SeqSBAIJ_7_inplace(Mat A, Vec bb, Vec xx)
    216: {
    217:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    218:   IS                 isrow = a->row;
    219:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *r, *vj;
    220:   PetscInt           nz, k, idx;
    221:   const MatScalar   *aa = a->a, *v, *d;
    222:   PetscScalar       *x, x0, x1, x2, x3, x4, x5, x6, *t, *tp;
    223:   const PetscScalar *b;

    225:   PetscFunctionBegin;
    226:   PetscCall(VecGetArrayRead(bb, &b));
    227:   PetscCall(VecGetArray(xx, &x));
    228:   t = a->solve_work;
    229:   PetscCall(ISGetIndices(isrow, &r));

    231:   /* solve U^T * D * y = b by forward substitution */
    232:   tp = t;
    233:   for (k = 0; k < mbs; k++) { /* t <- perm(b) */
    234:     idx   = 7 * r[k];
    235:     tp[0] = b[idx];
    236:     tp[1] = b[idx + 1];
    237:     tp[2] = b[idx + 2];
    238:     tp[3] = b[idx + 3];
    239:     tp[4] = b[idx + 4];
    240:     tp[5] = b[idx + 5];
    241:     tp[6] = b[idx + 6];
    242:     tp += 7;
    243:   }

    245:   for (k = 0; k < mbs; k++) {
    246:     v  = aa + 49 * ai[k];
    247:     vj = aj + ai[k];
    248:     tp = t + k * 7;
    249:     x0 = tp[0];
    250:     x1 = tp[1];
    251:     x2 = tp[2];
    252:     x3 = tp[3];
    253:     x4 = tp[4];
    254:     x5 = tp[5];
    255:     x6 = tp[6];
    256:     nz = ai[k + 1] - ai[k];
    257:     tp = t + (*vj) * 7;
    258:     while (nz--) {
    259:       tp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3 + v[4] * x4 + v[5] * x5 + v[6] * x6;
    260:       tp[1] += v[7] * x0 + v[8] * x1 + v[9] * x2 + v[10] * x3 + v[11] * x4 + v[12] * x5 + v[13] * x6;
    261:       tp[2] += v[14] * x0 + v[15] * x1 + v[16] * x2 + v[17] * x3 + v[18] * x4 + v[19] * x5 + v[20] * x6;
    262:       tp[3] += v[21] * x0 + v[22] * x1 + v[23] * x2 + v[24] * x3 + v[25] * x4 + v[26] * x5 + v[27] * x6;
    263:       tp[4] += v[28] * x0 + v[29] * x1 + v[30] * x2 + v[31] * x3 + v[32] * x4 + v[33] * x5 + v[34] * x6;
    264:       tp[5] += v[35] * x0 + v[36] * x1 + v[37] * x2 + v[38] * x3 + v[39] * x4 + v[40] * x5 + v[41] * x6;
    265:       tp[6] += v[42] * x0 + v[43] * x1 + v[44] * x2 + v[45] * x3 + v[46] * x4 + v[47] * x5 + v[48] * x6;
    266:       vj++;
    267:       tp = t + (*vj) * 7;
    268:       v += 49;
    269:     }

    271:     /* xk = inv(Dk)*(Dk*xk) */
    272:     d     = aa + k * 49; /* ptr to inv(Dk) */
    273:     tp    = t + k * 7;
    274:     tp[0] = d[0] * x0 + d[7] * x1 + d[14] * x2 + d[21] * x3 + d[28] * x4 + d[35] * x5 + d[42] * x6;
    275:     tp[1] = d[1] * x0 + d[8] * x1 + d[15] * x2 + d[22] * x3 + d[29] * x4 + d[36] * x5 + d[43] * x6;
    276:     tp[2] = d[2] * x0 + d[9] * x1 + d[16] * x2 + d[23] * x3 + d[30] * x4 + d[37] * x5 + d[44] * x6;
    277:     tp[3] = d[3] * x0 + d[10] * x1 + d[17] * x2 + d[24] * x3 + d[31] * x4 + d[38] * x5 + d[45] * x6;
    278:     tp[4] = d[4] * x0 + d[11] * x1 + d[18] * x2 + d[25] * x3 + d[32] * x4 + d[39] * x5 + d[46] * x6;
    279:     tp[5] = d[5] * x0 + d[12] * x1 + d[19] * x2 + d[26] * x3 + d[33] * x4 + d[40] * x5 + d[47] * x6;
    280:     tp[6] = d[6] * x0 + d[13] * x1 + d[20] * x2 + d[27] * x3 + d[34] * x4 + d[41] * x5 + d[48] * x6;
    281:   }

    283:   /* solve U*x = y by back substitution */
    284:   for (k = mbs - 1; k >= 0; k--) {
    285:     v  = aa + 49 * ai[k];
    286:     vj = aj + ai[k];
    287:     tp = t + k * 7;
    288:     x0 = tp[0];
    289:     x1 = tp[1];
    290:     x2 = tp[2];
    291:     x3 = tp[3];
    292:     x4 = tp[4];
    293:     x5 = tp[5];
    294:     x6 = tp[6]; /* xk */
    295:     nz = ai[k + 1] - ai[k];

    297:     tp = t + (*vj) * 7;
    298:     while (nz--) {
    299:       /* xk += U(k,:)*x(:) */
    300:       x0 += v[0] * tp[0] + v[7] * tp[1] + v[14] * tp[2] + v[21] * tp[3] + v[28] * tp[4] + v[35] * tp[5] + v[42] * tp[6];
    301:       x1 += v[1] * tp[0] + v[8] * tp[1] + v[15] * tp[2] + v[22] * tp[3] + v[29] * tp[4] + v[36] * tp[5] + v[43] * tp[6];
    302:       x2 += v[2] * tp[0] + v[9] * tp[1] + v[16] * tp[2] + v[23] * tp[3] + v[30] * tp[4] + v[37] * tp[5] + v[44] * tp[6];
    303:       x3 += v[3] * tp[0] + v[10] * tp[1] + v[17] * tp[2] + v[24] * tp[3] + v[31] * tp[4] + v[38] * tp[5] + v[45] * tp[6];
    304:       x4 += v[4] * tp[0] + v[11] * tp[1] + v[18] * tp[2] + v[25] * tp[3] + v[32] * tp[4] + v[39] * tp[5] + v[46] * tp[6];
    305:       x5 += v[5] * tp[0] + v[12] * tp[1] + v[19] * tp[2] + v[26] * tp[3] + v[33] * tp[4] + v[40] * tp[5] + v[47] * tp[6];
    306:       x6 += v[6] * tp[0] + v[13] * tp[1] + v[20] * tp[2] + v[27] * tp[3] + v[34] * tp[4] + v[41] * tp[5] + v[48] * tp[6];
    307:       vj++;
    308:       tp = t + (*vj) * 7;
    309:       v += 49;
    310:     }
    311:     tp         = t + k * 7;
    312:     tp[0]      = x0;
    313:     tp[1]      = x1;
    314:     tp[2]      = x2;
    315:     tp[3]      = x3;
    316:     tp[4]      = x4;
    317:     tp[5]      = x5;
    318:     tp[6]      = x6;
    319:     idx        = 7 * r[k];
    320:     x[idx]     = x0;
    321:     x[idx + 1] = x1;
    322:     x[idx + 2] = x2;
    323:     x[idx + 3] = x3;
    324:     x[idx + 4] = x4;
    325:     x[idx + 5] = x5;
    326:     x[idx + 6] = x6;
    327:   }

    329:   PetscCall(ISRestoreIndices(isrow, &r));
    330:   PetscCall(VecRestoreArrayRead(bb, &b));
    331:   PetscCall(VecRestoreArray(xx, &x));
    332:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    333:   PetscFunctionReturn(PETSC_SUCCESS);
    334: }

    336: static PetscErrorCode MatForwardSolve_SeqSBAIJ_7_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    337: {
    338:   const MatScalar *v, *d;
    339:   PetscScalar     *xp, x0, x1, x2, x3, x4, x5, x6;
    340:   PetscInt         nz, k;
    341:   const PetscInt  *vj;

    343:   PetscFunctionBegin;
    344:   for (k = 0; k < mbs; k++) {
    345:     v  = aa + 49 * ai[k];
    346:     xp = x + k * 7;
    347:     x0 = xp[0];
    348:     x1 = xp[1];
    349:     x2 = xp[2];
    350:     x3 = xp[3];
    351:     x4 = xp[4];
    352:     x5 = xp[5];
    353:     x6 = xp[6]; /* Dk*xk = k-th block of x */
    354:     nz = ai[k + 1] - ai[k];
    355:     vj = aj + ai[k];
    356:     PetscPrefetchBlock(vj + nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    357:     PetscPrefetchBlock(v + 49 * nz, 49 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    358:     while (nz--) {
    359:       xp = x + (*vj) * 7;
    360:       /* x(:) += U(k,:)^T*(Dk*xk) */
    361:       xp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3 + v[4] * x4 + v[5] * x5 + v[6] * x6;
    362:       xp[1] += v[7] * x0 + v[8] * x1 + v[9] * x2 + v[10] * x3 + v[11] * x4 + v[12] * x5 + v[13] * x6;
    363:       xp[2] += v[14] * x0 + v[15] * x1 + v[16] * x2 + v[17] * x3 + v[18] * x4 + v[19] * x5 + v[20] * x6;
    364:       xp[3] += v[21] * x0 + v[22] * x1 + v[23] * x2 + v[24] * x3 + v[25] * x4 + v[26] * x5 + v[27] * x6;
    365:       xp[4] += v[28] * x0 + v[29] * x1 + v[30] * x2 + v[31] * x3 + v[32] * x4 + v[33] * x5 + v[34] * x6;
    366:       xp[5] += v[35] * x0 + v[36] * x1 + v[37] * x2 + v[38] * x3 + v[39] * x4 + v[40] * x5 + v[41] * x6;
    367:       xp[6] += v[42] * x0 + v[43] * x1 + v[44] * x2 + v[45] * x3 + v[46] * x4 + v[47] * x5 + v[48] * x6;
    368:       vj++;
    369:       v += 49;
    370:     }
    371:     /* xk = inv(Dk)*(Dk*xk) */
    372:     d     = aa + k * 49; /* ptr to inv(Dk) */
    373:     xp    = x + k * 7;
    374:     xp[0] = d[0] * x0 + d[7] * x1 + d[14] * x2 + d[21] * x3 + d[28] * x4 + d[35] * x5 + d[42] * x6;
    375:     xp[1] = d[1] * x0 + d[8] * x1 + d[15] * x2 + d[22] * x3 + d[29] * x4 + d[36] * x5 + d[43] * x6;
    376:     xp[2] = d[2] * x0 + d[9] * x1 + d[16] * x2 + d[23] * x3 + d[30] * x4 + d[37] * x5 + d[44] * x6;
    377:     xp[3] = d[3] * x0 + d[10] * x1 + d[17] * x2 + d[24] * x3 + d[31] * x4 + d[38] * x5 + d[45] * x6;
    378:     xp[4] = d[4] * x0 + d[11] * x1 + d[18] * x2 + d[25] * x3 + d[32] * x4 + d[39] * x5 + d[46] * x6;
    379:     xp[5] = d[5] * x0 + d[12] * x1 + d[19] * x2 + d[26] * x3 + d[33] * x4 + d[40] * x5 + d[47] * x6;
    380:     xp[6] = d[6] * x0 + d[13] * x1 + d[20] * x2 + d[27] * x3 + d[34] * x4 + d[41] * x5 + d[48] * x6;
    381:   }
    382:   PetscFunctionReturn(PETSC_SUCCESS);
    383: }

    385: static PetscErrorCode MatBackwardSolve_SeqSBAIJ_7_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    386: {
    387:   const MatScalar *v;
    388:   PetscScalar     *xp, x0, x1, x2, x3, x4, x5, x6;
    389:   PetscInt         nz, k;
    390:   const PetscInt  *vj;

    392:   PetscFunctionBegin;
    393:   for (k = mbs - 1; k >= 0; k--) {
    394:     v  = aa + 49 * ai[k];
    395:     xp = x + k * 7;
    396:     x0 = xp[0];
    397:     x1 = xp[1];
    398:     x2 = xp[2];
    399:     x3 = xp[3];
    400:     x4 = xp[4];
    401:     x5 = xp[5];
    402:     x6 = xp[6]; /* xk */
    403:     nz = ai[k + 1] - ai[k];
    404:     vj = aj + ai[k];
    405:     PetscPrefetchBlock(vj - nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    406:     PetscPrefetchBlock(v - 49 * nz, 49 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    407:     while (nz--) {
    408:       xp = x + (*vj) * 7;
    409:       /* xk += U(k,:)*x(:) */
    410:       x0 += v[0] * xp[0] + v[7] * xp[1] + v[14] * xp[2] + v[21] * xp[3] + v[28] * xp[4] + v[35] * xp[5] + v[42] * xp[6];
    411:       x1 += v[1] * xp[0] + v[8] * xp[1] + v[15] * xp[2] + v[22] * xp[3] + v[29] * xp[4] + v[36] * xp[5] + v[43] * xp[6];
    412:       x2 += v[2] * xp[0] + v[9] * xp[1] + v[16] * xp[2] + v[23] * xp[3] + v[30] * xp[4] + v[37] * xp[5] + v[44] * xp[6];
    413:       x3 += v[3] * xp[0] + v[10] * xp[1] + v[17] * xp[2] + v[24] * xp[3] + v[31] * xp[4] + v[38] * xp[5] + v[45] * xp[6];
    414:       x4 += v[4] * xp[0] + v[11] * xp[1] + v[18] * xp[2] + v[25] * xp[3] + v[32] * xp[4] + v[39] * xp[5] + v[46] * xp[6];
    415:       x5 += v[5] * xp[0] + v[12] * xp[1] + v[19] * xp[2] + v[26] * xp[3] + v[33] * xp[4] + v[40] * xp[5] + v[47] * xp[6];
    416:       x6 += v[6] * xp[0] + v[13] * xp[1] + v[20] * xp[2] + v[27] * xp[3] + v[34] * xp[4] + v[41] * xp[5] + v[48] * xp[6];
    417:       vj++;
    418:       v += 49;
    419:     }
    420:     xp    = x + k * 7;
    421:     xp[0] = x0;
    422:     xp[1] = x1;
    423:     xp[2] = x2;
    424:     xp[3] = x3;
    425:     xp[4] = x4;
    426:     xp[5] = x5;
    427:     xp[6] = x6;
    428:   }
    429:   PetscFunctionReturn(PETSC_SUCCESS);
    430: }

    432: PetscErrorCode MatSolve_SeqSBAIJ_7_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    433: {
    434:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    435:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    436:   const MatScalar   *aa = a->a;
    437:   PetscScalar       *x;
    438:   const PetscScalar *b;

    440:   PetscFunctionBegin;
    441:   PetscCall(VecGetArrayRead(bb, &b));
    442:   PetscCall(VecGetArray(xx, &x));

    444:   /* solve U^T * D * y = b by forward substitution */
    445:   PetscCall(PetscArraycpy(x, b, 7 * mbs)); /* x <- b */
    446:   PetscCall(MatForwardSolve_SeqSBAIJ_7_NaturalOrdering(ai, aj, aa, mbs, x));

    448:   /* solve U*x = y by back substitution */
    449:   PetscCall(MatBackwardSolve_SeqSBAIJ_7_NaturalOrdering(ai, aj, aa, mbs, x));

    451:   PetscCall(VecRestoreArrayRead(bb, &b));
    452:   PetscCall(VecRestoreArray(xx, &x));
    453:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    454:   PetscFunctionReturn(PETSC_SUCCESS);
    455: }

    457: PetscErrorCode MatForwardSolve_SeqSBAIJ_7_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    458: {
    459:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    460:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    461:   const MatScalar   *aa = a->a;
    462:   PetscScalar       *x;
    463:   const PetscScalar *b;

    465:   PetscFunctionBegin;
    466:   PetscCall(VecGetArrayRead(bb, &b));
    467:   PetscCall(VecGetArray(xx, &x));
    468:   PetscCall(PetscArraycpy(x, b, 7 * mbs));
    469:   PetscCall(MatForwardSolve_SeqSBAIJ_7_NaturalOrdering(ai, aj, aa, mbs, x));
    470:   PetscCall(VecRestoreArrayRead(bb, &b));
    471:   PetscCall(VecRestoreArray(xx, &x));
    472:   PetscCall(PetscLogFlops(2.0 * a->bs2 * a->nz - A->rmap->bs * mbs));
    473:   PetscFunctionReturn(PETSC_SUCCESS);
    474: }

    476: PetscErrorCode MatBackwardSolve_SeqSBAIJ_7_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    477: {
    478:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    479:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    480:   const MatScalar   *aa = a->a;
    481:   PetscScalar       *x;
    482:   const PetscScalar *b;

    484:   PetscFunctionBegin;
    485:   PetscCall(VecGetArrayRead(bb, &b));
    486:   PetscCall(VecGetArray(xx, &x));
    487:   PetscCall(PetscArraycpy(x, b, 7 * mbs));
    488:   PetscCall(MatBackwardSolve_SeqSBAIJ_7_NaturalOrdering(ai, aj, aa, mbs, x));
    489:   PetscCall(VecRestoreArrayRead(bb, &b));
    490:   PetscCall(VecRestoreArray(xx, &x));
    491:   PetscCall(PetscLogFlops(2.0 * a->bs2 * (a->nz - mbs)));
    492:   PetscFunctionReturn(PETSC_SUCCESS);
    493: }

    495: PetscErrorCode MatSolve_SeqSBAIJ_6_inplace(Mat A, Vec bb, Vec xx)
    496: {
    497:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    498:   IS                 isrow = a->row;
    499:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *r, *vj;
    500:   PetscInt           nz, k, idx;
    501:   const MatScalar   *aa = a->a, *v, *d;
    502:   PetscScalar       *x, x0, x1, x2, x3, x4, x5, *t, *tp;
    503:   const PetscScalar *b;

    505:   PetscFunctionBegin;
    506:   PetscCall(VecGetArrayRead(bb, &b));
    507:   PetscCall(VecGetArray(xx, &x));
    508:   t = a->solve_work;
    509:   PetscCall(ISGetIndices(isrow, &r));

    511:   /* solve U^T * D * y = b by forward substitution */
    512:   tp = t;
    513:   for (k = 0; k < mbs; k++) { /* t <- perm(b) */
    514:     idx   = 6 * r[k];
    515:     tp[0] = b[idx];
    516:     tp[1] = b[idx + 1];
    517:     tp[2] = b[idx + 2];
    518:     tp[3] = b[idx + 3];
    519:     tp[4] = b[idx + 4];
    520:     tp[5] = b[idx + 5];
    521:     tp += 6;
    522:   }

    524:   for (k = 0; k < mbs; k++) {
    525:     v  = aa + 36 * ai[k];
    526:     vj = aj + ai[k];
    527:     tp = t + k * 6;
    528:     x0 = tp[0];
    529:     x1 = tp[1];
    530:     x2 = tp[2];
    531:     x3 = tp[3];
    532:     x4 = tp[4];
    533:     x5 = tp[5];
    534:     nz = ai[k + 1] - ai[k];
    535:     tp = t + (*vj) * 6;
    536:     while (nz--) {
    537:       tp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3 + v[4] * x4 + v[5] * x5;
    538:       tp[1] += v[6] * x0 + v[7] * x1 + v[8] * x2 + v[9] * x3 + v[10] * x4 + v[11] * x5;
    539:       tp[2] += v[12] * x0 + v[13] * x1 + v[14] * x2 + v[15] * x3 + v[16] * x4 + v[17] * x5;
    540:       tp[3] += v[18] * x0 + v[19] * x1 + v[20] * x2 + v[21] * x3 + v[22] * x4 + v[23] * x5;
    541:       tp[4] += v[24] * x0 + v[25] * x1 + v[26] * x2 + v[27] * x3 + v[28] * x4 + v[29] * x5;
    542:       tp[5] += v[30] * x0 + v[31] * x1 + v[32] * x2 + v[33] * x3 + v[34] * x4 + v[35] * x5;
    543:       vj++;
    544:       tp = t + (*vj) * 6;
    545:       v += 36;
    546:     }

    548:     /* xk = inv(Dk)*(Dk*xk) */
    549:     d     = aa + k * 36; /* ptr to inv(Dk) */
    550:     tp    = t + k * 6;
    551:     tp[0] = d[0] * x0 + d[6] * x1 + d[12] * x2 + d[18] * x3 + d[24] * x4 + d[30] * x5;
    552:     tp[1] = d[1] * x0 + d[7] * x1 + d[13] * x2 + d[19] * x3 + d[25] * x4 + d[31] * x5;
    553:     tp[2] = d[2] * x0 + d[8] * x1 + d[14] * x2 + d[20] * x3 + d[26] * x4 + d[32] * x5;
    554:     tp[3] = d[3] * x0 + d[9] * x1 + d[15] * x2 + d[21] * x3 + d[27] * x4 + d[33] * x5;
    555:     tp[4] = d[4] * x0 + d[10] * x1 + d[16] * x2 + d[22] * x3 + d[28] * x4 + d[34] * x5;
    556:     tp[5] = d[5] * x0 + d[11] * x1 + d[17] * x2 + d[23] * x3 + d[29] * x4 + d[35] * x5;
    557:   }

    559:   /* solve U*x = y by back substitution */
    560:   for (k = mbs - 1; k >= 0; k--) {
    561:     v  = aa + 36 * ai[k];
    562:     vj = aj + ai[k];
    563:     tp = t + k * 6;
    564:     x0 = tp[0];
    565:     x1 = tp[1];
    566:     x2 = tp[2];
    567:     x3 = tp[3];
    568:     x4 = tp[4];
    569:     x5 = tp[5]; /* xk */
    570:     nz = ai[k + 1] - ai[k];

    572:     tp = t + (*vj) * 6;
    573:     while (nz--) {
    574:       /* xk += U(k,:)*x(:) */
    575:       x0 += v[0] * tp[0] + v[6] * tp[1] + v[12] * tp[2] + v[18] * tp[3] + v[24] * tp[4] + v[30] * tp[5];
    576:       x1 += v[1] * tp[0] + v[7] * tp[1] + v[13] * tp[2] + v[19] * tp[3] + v[25] * tp[4] + v[31] * tp[5];
    577:       x2 += v[2] * tp[0] + v[8] * tp[1] + v[14] * tp[2] + v[20] * tp[3] + v[26] * tp[4] + v[32] * tp[5];
    578:       x3 += v[3] * tp[0] + v[9] * tp[1] + v[15] * tp[2] + v[21] * tp[3] + v[27] * tp[4] + v[33] * tp[5];
    579:       x4 += v[4] * tp[0] + v[10] * tp[1] + v[16] * tp[2] + v[22] * tp[3] + v[28] * tp[4] + v[34] * tp[5];
    580:       x5 += v[5] * tp[0] + v[11] * tp[1] + v[17] * tp[2] + v[23] * tp[3] + v[29] * tp[4] + v[35] * tp[5];
    581:       vj++;
    582:       tp = t + (*vj) * 6;
    583:       v += 36;
    584:     }
    585:     tp         = t + k * 6;
    586:     tp[0]      = x0;
    587:     tp[1]      = x1;
    588:     tp[2]      = x2;
    589:     tp[3]      = x3;
    590:     tp[4]      = x4;
    591:     tp[5]      = x5;
    592:     idx        = 6 * r[k];
    593:     x[idx]     = x0;
    594:     x[idx + 1] = x1;
    595:     x[idx + 2] = x2;
    596:     x[idx + 3] = x3;
    597:     x[idx + 4] = x4;
    598:     x[idx + 5] = x5;
    599:   }

    601:   PetscCall(ISRestoreIndices(isrow, &r));
    602:   PetscCall(VecRestoreArrayRead(bb, &b));
    603:   PetscCall(VecRestoreArray(xx, &x));
    604:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    605:   PetscFunctionReturn(PETSC_SUCCESS);
    606: }

    608: static PetscErrorCode MatForwardSolve_SeqSBAIJ_6_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    609: {
    610:   const MatScalar *v, *d;
    611:   PetscScalar     *xp, x0, x1, x2, x3, x4, x5;
    612:   PetscInt         nz, k;
    613:   const PetscInt  *vj;

    615:   PetscFunctionBegin;
    616:   for (k = 0; k < mbs; k++) {
    617:     v  = aa + 36 * ai[k];
    618:     xp = x + k * 6;
    619:     x0 = xp[0];
    620:     x1 = xp[1];
    621:     x2 = xp[2];
    622:     x3 = xp[3];
    623:     x4 = xp[4];
    624:     x5 = xp[5]; /* Dk*xk = k-th block of x */
    625:     nz = ai[k + 1] - ai[k];
    626:     vj = aj + ai[k];
    627:     PetscPrefetchBlock(vj + nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    628:     PetscPrefetchBlock(v + 36 * nz, 36 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    629:     while (nz--) {
    630:       xp = x + (*vj) * 6;
    631:       /* x(:) += U(k,:)^T*(Dk*xk) */
    632:       xp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3 + v[4] * x4 + v[5] * x5;
    633:       xp[1] += v[6] * x0 + v[7] * x1 + v[8] * x2 + v[9] * x3 + v[10] * x4 + v[11] * x5;
    634:       xp[2] += v[12] * x0 + v[13] * x1 + v[14] * x2 + v[15] * x3 + v[16] * x4 + v[17] * x5;
    635:       xp[3] += v[18] * x0 + v[19] * x1 + v[20] * x2 + v[21] * x3 + v[22] * x4 + v[23] * x5;
    636:       xp[4] += v[24] * x0 + v[25] * x1 + v[26] * x2 + v[27] * x3 + v[28] * x4 + v[29] * x5;
    637:       xp[5] += v[30] * x0 + v[31] * x1 + v[32] * x2 + v[33] * x3 + v[34] * x4 + v[35] * x5;
    638:       vj++;
    639:       v += 36;
    640:     }
    641:     /* xk = inv(Dk)*(Dk*xk) */
    642:     d     = aa + k * 36; /* ptr to inv(Dk) */
    643:     xp    = x + k * 6;
    644:     xp[0] = d[0] * x0 + d[6] * x1 + d[12] * x2 + d[18] * x3 + d[24] * x4 + d[30] * x5;
    645:     xp[1] = d[1] * x0 + d[7] * x1 + d[13] * x2 + d[19] * x3 + d[25] * x4 + d[31] * x5;
    646:     xp[2] = d[2] * x0 + d[8] * x1 + d[14] * x2 + d[20] * x3 + d[26] * x4 + d[32] * x5;
    647:     xp[3] = d[3] * x0 + d[9] * x1 + d[15] * x2 + d[21] * x3 + d[27] * x4 + d[33] * x5;
    648:     xp[4] = d[4] * x0 + d[10] * x1 + d[16] * x2 + d[22] * x3 + d[28] * x4 + d[34] * x5;
    649:     xp[5] = d[5] * x0 + d[11] * x1 + d[17] * x2 + d[23] * x3 + d[29] * x4 + d[35] * x5;
    650:   }
    651:   PetscFunctionReturn(PETSC_SUCCESS);
    652: }
    653: static PetscErrorCode MatBackwardSolve_SeqSBAIJ_6_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    654: {
    655:   const MatScalar *v;
    656:   PetscScalar     *xp, x0, x1, x2, x3, x4, x5;
    657:   PetscInt         nz, k;
    658:   const PetscInt  *vj;

    660:   PetscFunctionBegin;
    661:   for (k = mbs - 1; k >= 0; k--) {
    662:     v  = aa + 36 * ai[k];
    663:     xp = x + k * 6;
    664:     x0 = xp[0];
    665:     x1 = xp[1];
    666:     x2 = xp[2];
    667:     x3 = xp[3];
    668:     x4 = xp[4];
    669:     x5 = xp[5]; /* xk */
    670:     nz = ai[k + 1] - ai[k];
    671:     vj = aj + ai[k];
    672:     PetscPrefetchBlock(vj - nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    673:     PetscPrefetchBlock(v - 36 * nz, 36 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    674:     while (nz--) {
    675:       xp = x + (*vj) * 6;
    676:       /* xk += U(k,:)*x(:) */
    677:       x0 += v[0] * xp[0] + v[6] * xp[1] + v[12] * xp[2] + v[18] * xp[3] + v[24] * xp[4] + v[30] * xp[5];
    678:       x1 += v[1] * xp[0] + v[7] * xp[1] + v[13] * xp[2] + v[19] * xp[3] + v[25] * xp[4] + v[31] * xp[5];
    679:       x2 += v[2] * xp[0] + v[8] * xp[1] + v[14] * xp[2] + v[20] * xp[3] + v[26] * xp[4] + v[32] * xp[5];
    680:       x3 += v[3] * xp[0] + v[9] * xp[1] + v[15] * xp[2] + v[21] * xp[3] + v[27] * xp[4] + v[33] * xp[5];
    681:       x4 += v[4] * xp[0] + v[10] * xp[1] + v[16] * xp[2] + v[22] * xp[3] + v[28] * xp[4] + v[34] * xp[5];
    682:       x5 += v[5] * xp[0] + v[11] * xp[1] + v[17] * xp[2] + v[23] * xp[3] + v[29] * xp[4] + v[35] * xp[5];
    683:       vj++;
    684:       v += 36;
    685:     }
    686:     xp    = x + k * 6;
    687:     xp[0] = x0;
    688:     xp[1] = x1;
    689:     xp[2] = x2;
    690:     xp[3] = x3;
    691:     xp[4] = x4;
    692:     xp[5] = x5;
    693:   }
    694:   PetscFunctionReturn(PETSC_SUCCESS);
    695: }

    697: PetscErrorCode MatSolve_SeqSBAIJ_6_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    698: {
    699:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    700:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    701:   const MatScalar   *aa = a->a;
    702:   PetscScalar       *x;
    703:   const PetscScalar *b;

    705:   PetscFunctionBegin;
    706:   PetscCall(VecGetArrayRead(bb, &b));
    707:   PetscCall(VecGetArray(xx, &x));

    709:   /* solve U^T * D * y = b by forward substitution */
    710:   PetscCall(PetscArraycpy(x, b, 6 * mbs)); /* x <- b */
    711:   PetscCall(MatForwardSolve_SeqSBAIJ_6_NaturalOrdering(ai, aj, aa, mbs, x));

    713:   /* solve U*x = y by back substitution */
    714:   PetscCall(MatBackwardSolve_SeqSBAIJ_6_NaturalOrdering(ai, aj, aa, mbs, x));

    716:   PetscCall(VecRestoreArrayRead(bb, &b));
    717:   PetscCall(VecRestoreArray(xx, &x));
    718:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    719:   PetscFunctionReturn(PETSC_SUCCESS);
    720: }

    722: PetscErrorCode MatForwardSolve_SeqSBAIJ_6_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    723: {
    724:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    725:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    726:   const MatScalar   *aa = a->a;
    727:   PetscScalar       *x;
    728:   const PetscScalar *b;

    730:   PetscFunctionBegin;
    731:   PetscCall(VecGetArrayRead(bb, &b));
    732:   PetscCall(VecGetArray(xx, &x));
    733:   PetscCall(PetscArraycpy(x, b, 6 * mbs)); /* x <- b */
    734:   PetscCall(MatForwardSolve_SeqSBAIJ_6_NaturalOrdering(ai, aj, aa, mbs, x));
    735:   PetscCall(VecRestoreArrayRead(bb, &b));
    736:   PetscCall(VecRestoreArray(xx, &x));
    737:   PetscCall(PetscLogFlops(2.0 * a->bs2 * a->nz - A->rmap->bs * mbs));
    738:   PetscFunctionReturn(PETSC_SUCCESS);
    739: }

    741: PetscErrorCode MatBackwardSolve_SeqSBAIJ_6_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    742: {
    743:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    744:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    745:   const MatScalar   *aa = a->a;
    746:   PetscScalar       *x;
    747:   const PetscScalar *b;

    749:   PetscFunctionBegin;
    750:   PetscCall(VecGetArrayRead(bb, &b));
    751:   PetscCall(VecGetArray(xx, &x));
    752:   PetscCall(PetscArraycpy(x, b, 6 * mbs)); /* x <- b */
    753:   PetscCall(MatBackwardSolve_SeqSBAIJ_6_NaturalOrdering(ai, aj, aa, mbs, x));
    754:   PetscCall(VecRestoreArrayRead(bb, &b));
    755:   PetscCall(VecRestoreArray(xx, &x));
    756:   PetscCall(PetscLogFlops(2.0 * a->bs2 * (a->nz - mbs)));
    757:   PetscFunctionReturn(PETSC_SUCCESS);
    758: }

    760: PetscErrorCode MatSolve_SeqSBAIJ_5_inplace(Mat A, Vec bb, Vec xx)
    761: {
    762:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    763:   IS                 isrow = a->row;
    764:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    765:   const PetscInt    *r, *vj;
    766:   PetscInt           nz, k, idx;
    767:   const MatScalar   *aa = a->a, *v, *diag;
    768:   PetscScalar       *x, x0, x1, x2, x3, x4, *t, *tp;
    769:   const PetscScalar *b;

    771:   PetscFunctionBegin;
    772:   PetscCall(VecGetArrayRead(bb, &b));
    773:   PetscCall(VecGetArray(xx, &x));
    774:   t = a->solve_work;
    775:   PetscCall(ISGetIndices(isrow, &r));

    777:   /* solve U^T * D * y = b by forward substitution */
    778:   tp = t;
    779:   for (k = 0; k < mbs; k++) { /* t <- perm(b) */
    780:     idx   = 5 * r[k];
    781:     tp[0] = b[idx];
    782:     tp[1] = b[idx + 1];
    783:     tp[2] = b[idx + 2];
    784:     tp[3] = b[idx + 3];
    785:     tp[4] = b[idx + 4];
    786:     tp += 5;
    787:   }

    789:   for (k = 0; k < mbs; k++) {
    790:     v  = aa + 25 * ai[k];
    791:     vj = aj + ai[k];
    792:     tp = t + k * 5;
    793:     x0 = tp[0];
    794:     x1 = tp[1];
    795:     x2 = tp[2];
    796:     x3 = tp[3];
    797:     x4 = tp[4];
    798:     nz = ai[k + 1] - ai[k];

    800:     tp = t + (*vj) * 5;
    801:     while (nz--) {
    802:       tp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3 + v[4] * x4;
    803:       tp[1] += v[5] * x0 + v[6] * x1 + v[7] * x2 + v[8] * x3 + v[9] * x4;
    804:       tp[2] += v[10] * x0 + v[11] * x1 + v[12] * x2 + v[13] * x3 + v[14] * x4;
    805:       tp[3] += v[15] * x0 + v[16] * x1 + v[17] * x2 + v[18] * x3 + v[19] * x4;
    806:       tp[4] += v[20] * x0 + v[21] * x1 + v[22] * x2 + v[23] * x3 + v[24] * x4;
    807:       vj++;
    808:       tp = t + (*vj) * 5;
    809:       v += 25;
    810:     }

    812:     /* xk = inv(Dk)*(Dk*xk) */
    813:     diag  = aa + k * 25; /* ptr to inv(Dk) */
    814:     tp    = t + k * 5;
    815:     tp[0] = diag[0] * x0 + diag[5] * x1 + diag[10] * x2 + diag[15] * x3 + diag[20] * x4;
    816:     tp[1] = diag[1] * x0 + diag[6] * x1 + diag[11] * x2 + diag[16] * x3 + diag[21] * x4;
    817:     tp[2] = diag[2] * x0 + diag[7] * x1 + diag[12] * x2 + diag[17] * x3 + diag[22] * x4;
    818:     tp[3] = diag[3] * x0 + diag[8] * x1 + diag[13] * x2 + diag[18] * x3 + diag[23] * x4;
    819:     tp[4] = diag[4] * x0 + diag[9] * x1 + diag[14] * x2 + diag[19] * x3 + diag[24] * x4;
    820:   }

    822:   /* solve U*x = y by back substitution */
    823:   for (k = mbs - 1; k >= 0; k--) {
    824:     v  = aa + 25 * ai[k];
    825:     vj = aj + ai[k];
    826:     tp = t + k * 5;
    827:     x0 = tp[0];
    828:     x1 = tp[1];
    829:     x2 = tp[2];
    830:     x3 = tp[3];
    831:     x4 = tp[4]; /* xk */
    832:     nz = ai[k + 1] - ai[k];

    834:     tp = t + (*vj) * 5;
    835:     while (nz--) {
    836:       /* xk += U(k,:)*x(:) */
    837:       x0 += v[0] * tp[0] + v[5] * tp[1] + v[10] * tp[2] + v[15] * tp[3] + v[20] * tp[4];
    838:       x1 += v[1] * tp[0] + v[6] * tp[1] + v[11] * tp[2] + v[16] * tp[3] + v[21] * tp[4];
    839:       x2 += v[2] * tp[0] + v[7] * tp[1] + v[12] * tp[2] + v[17] * tp[3] + v[22] * tp[4];
    840:       x3 += v[3] * tp[0] + v[8] * tp[1] + v[13] * tp[2] + v[18] * tp[3] + v[23] * tp[4];
    841:       x4 += v[4] * tp[0] + v[9] * tp[1] + v[14] * tp[2] + v[19] * tp[3] + v[24] * tp[4];
    842:       vj++;
    843:       tp = t + (*vj) * 5;
    844:       v += 25;
    845:     }
    846:     tp         = t + k * 5;
    847:     tp[0]      = x0;
    848:     tp[1]      = x1;
    849:     tp[2]      = x2;
    850:     tp[3]      = x3;
    851:     tp[4]      = x4;
    852:     idx        = 5 * r[k];
    853:     x[idx]     = x0;
    854:     x[idx + 1] = x1;
    855:     x[idx + 2] = x2;
    856:     x[idx + 3] = x3;
    857:     x[idx + 4] = x4;
    858:   }

    860:   PetscCall(ISRestoreIndices(isrow, &r));
    861:   PetscCall(VecRestoreArrayRead(bb, &b));
    862:   PetscCall(VecRestoreArray(xx, &x));
    863:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    864:   PetscFunctionReturn(PETSC_SUCCESS);
    865: }

    867: static PetscErrorCode MatForwardSolve_SeqSBAIJ_5_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    868: {
    869:   const MatScalar *v, *diag;
    870:   PetscScalar     *xp, x0, x1, x2, x3, x4;
    871:   PetscInt         nz, k;
    872:   const PetscInt  *vj;

    874:   PetscFunctionBegin;
    875:   for (k = 0; k < mbs; k++) {
    876:     v  = aa + 25 * ai[k];
    877:     xp = x + k * 5;
    878:     x0 = xp[0];
    879:     x1 = xp[1];
    880:     x2 = xp[2];
    881:     x3 = xp[3];
    882:     x4 = xp[4]; /* Dk*xk = k-th block of x */
    883:     nz = ai[k + 1] - ai[k];
    884:     vj = aj + ai[k];
    885:     PetscPrefetchBlock(vj + nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    886:     PetscPrefetchBlock(v + 25 * nz, 25 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    887:     while (nz--) {
    888:       xp = x + (*vj) * 5;
    889:       /* x(:) += U(k,:)^T*(Dk*xk) */
    890:       xp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3 + v[4] * x4;
    891:       xp[1] += v[5] * x0 + v[6] * x1 + v[7] * x2 + v[8] * x3 + v[9] * x4;
    892:       xp[2] += v[10] * x0 + v[11] * x1 + v[12] * x2 + v[13] * x3 + v[14] * x4;
    893:       xp[3] += v[15] * x0 + v[16] * x1 + v[17] * x2 + v[18] * x3 + v[19] * x4;
    894:       xp[4] += v[20] * x0 + v[21] * x1 + v[22] * x2 + v[23] * x3 + v[24] * x4;
    895:       vj++;
    896:       v += 25;
    897:     }
    898:     /* xk = inv(Dk)*(Dk*xk) */
    899:     diag  = aa + k * 25; /* ptr to inv(Dk) */
    900:     xp    = x + k * 5;
    901:     xp[0] = diag[0] * x0 + diag[5] * x1 + diag[10] * x2 + diag[15] * x3 + diag[20] * x4;
    902:     xp[1] = diag[1] * x0 + diag[6] * x1 + diag[11] * x2 + diag[16] * x3 + diag[21] * x4;
    903:     xp[2] = diag[2] * x0 + diag[7] * x1 + diag[12] * x2 + diag[17] * x3 + diag[22] * x4;
    904:     xp[3] = diag[3] * x0 + diag[8] * x1 + diag[13] * x2 + diag[18] * x3 + diag[23] * x4;
    905:     xp[4] = diag[4] * x0 + diag[9] * x1 + diag[14] * x2 + diag[19] * x3 + diag[24] * x4;
    906:   }
    907:   PetscFunctionReturn(PETSC_SUCCESS);
    908: }

    910: static PetscErrorCode MatBackwardSolve_SeqSBAIJ_5_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    911: {
    912:   const MatScalar *v;
    913:   PetscScalar     *xp, x0, x1, x2, x3, x4;
    914:   PetscInt         nz, k;
    915:   const PetscInt  *vj;

    917:   PetscFunctionBegin;
    918:   for (k = mbs - 1; k >= 0; k--) {
    919:     v  = aa + 25 * ai[k];
    920:     xp = x + k * 5;
    921:     x0 = xp[0];
    922:     x1 = xp[1];
    923:     x2 = xp[2];
    924:     x3 = xp[3];
    925:     x4 = xp[4]; /* xk */
    926:     nz = ai[k + 1] - ai[k];
    927:     vj = aj + ai[k];
    928:     PetscPrefetchBlock(vj - nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    929:     PetscPrefetchBlock(v - 25 * nz, 25 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    930:     while (nz--) {
    931:       xp = x + (*vj) * 5;
    932:       /* xk += U(k,:)*x(:) */
    933:       x0 += v[0] * xp[0] + v[5] * xp[1] + v[10] * xp[2] + v[15] * xp[3] + v[20] * xp[4];
    934:       x1 += v[1] * xp[0] + v[6] * xp[1] + v[11] * xp[2] + v[16] * xp[3] + v[21] * xp[4];
    935:       x2 += v[2] * xp[0] + v[7] * xp[1] + v[12] * xp[2] + v[17] * xp[3] + v[22] * xp[4];
    936:       x3 += v[3] * xp[0] + v[8] * xp[1] + v[13] * xp[2] + v[18] * xp[3] + v[23] * xp[4];
    937:       x4 += v[4] * xp[0] + v[9] * xp[1] + v[14] * xp[2] + v[19] * xp[3] + v[24] * xp[4];
    938:       vj++;
    939:       v += 25;
    940:     }
    941:     xp    = x + k * 5;
    942:     xp[0] = x0;
    943:     xp[1] = x1;
    944:     xp[2] = x2;
    945:     xp[3] = x3;
    946:     xp[4] = x4;
    947:   }
    948:   PetscFunctionReturn(PETSC_SUCCESS);
    949: }

    951: PetscErrorCode MatSolve_SeqSBAIJ_5_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    952: {
    953:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    954:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    955:   const MatScalar   *aa = a->a;
    956:   PetscScalar       *x;
    957:   const PetscScalar *b;

    959:   PetscFunctionBegin;
    960:   PetscCall(VecGetArrayRead(bb, &b));
    961:   PetscCall(VecGetArray(xx, &x));

    963:   /* solve U^T * D * y = b by forward substitution */
    964:   PetscCall(PetscArraycpy(x, b, 5 * mbs)); /* x <- b */
    965:   PetscCall(MatForwardSolve_SeqSBAIJ_5_NaturalOrdering(ai, aj, aa, mbs, x));

    967:   /* solve U*x = y by back substitution */
    968:   PetscCall(MatBackwardSolve_SeqSBAIJ_5_NaturalOrdering(ai, aj, aa, mbs, x));

    970:   PetscCall(VecRestoreArrayRead(bb, &b));
    971:   PetscCall(VecRestoreArray(xx, &x));
    972:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    973:   PetscFunctionReturn(PETSC_SUCCESS);
    974: }

    976: PetscErrorCode MatForwardSolve_SeqSBAIJ_5_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    977: {
    978:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    979:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    980:   const MatScalar   *aa = a->a;
    981:   PetscScalar       *x;
    982:   const PetscScalar *b;

    984:   PetscFunctionBegin;
    985:   PetscCall(VecGetArrayRead(bb, &b));
    986:   PetscCall(VecGetArray(xx, &x));
    987:   PetscCall(PetscArraycpy(x, b, 5 * mbs)); /* x <- b */
    988:   PetscCall(MatForwardSolve_SeqSBAIJ_5_NaturalOrdering(ai, aj, aa, mbs, x));
    989:   PetscCall(VecRestoreArrayRead(bb, &b));
    990:   PetscCall(VecRestoreArray(xx, &x));
    991:   PetscCall(PetscLogFlops(2.0 * a->bs2 * a->nz - A->rmap->bs * mbs));
    992:   PetscFunctionReturn(PETSC_SUCCESS);
    993: }

    995: PetscErrorCode MatBackwardSolve_SeqSBAIJ_5_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    996: {
    997:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    998:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    999:   const MatScalar   *aa = a->a;
    1000:   PetscScalar       *x;
    1001:   const PetscScalar *b;

    1003:   PetscFunctionBegin;
    1004:   PetscCall(VecGetArrayRead(bb, &b));
    1005:   PetscCall(VecGetArray(xx, &x));
    1006:   PetscCall(PetscArraycpy(x, b, 5 * mbs));
    1007:   PetscCall(MatBackwardSolve_SeqSBAIJ_5_NaturalOrdering(ai, aj, aa, mbs, x));
    1008:   PetscCall(VecRestoreArrayRead(bb, &b));
    1009:   PetscCall(VecRestoreArray(xx, &x));
    1010:   PetscCall(PetscLogFlops(2.0 * a->bs2 * (a->nz - mbs)));
    1011:   PetscFunctionReturn(PETSC_SUCCESS);
    1012: }

    1014: PetscErrorCode MatSolve_SeqSBAIJ_4_inplace(Mat A, Vec bb, Vec xx)
    1015: {
    1016:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1017:   IS                 isrow = a->row;
    1018:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1019:   const PetscInt    *r, *vj;
    1020:   PetscInt           nz, k, idx;
    1021:   const MatScalar   *aa = a->a, *v, *diag;
    1022:   PetscScalar       *x, x0, x1, x2, x3, *t, *tp;
    1023:   const PetscScalar *b;

    1025:   PetscFunctionBegin;
    1026:   PetscCall(VecGetArrayRead(bb, &b));
    1027:   PetscCall(VecGetArray(xx, &x));
    1028:   t = a->solve_work;
    1029:   PetscCall(ISGetIndices(isrow, &r));

    1031:   /* solve U^T * D * y = b by forward substitution */
    1032:   tp = t;
    1033:   for (k = 0; k < mbs; k++) { /* t <- perm(b) */
    1034:     idx   = 4 * r[k];
    1035:     tp[0] = b[idx];
    1036:     tp[1] = b[idx + 1];
    1037:     tp[2] = b[idx + 2];
    1038:     tp[3] = b[idx + 3];
    1039:     tp += 4;
    1040:   }

    1042:   for (k = 0; k < mbs; k++) {
    1043:     v  = aa + 16 * ai[k];
    1044:     vj = aj + ai[k];
    1045:     tp = t + k * 4;
    1046:     x0 = tp[0];
    1047:     x1 = tp[1];
    1048:     x2 = tp[2];
    1049:     x3 = tp[3];
    1050:     nz = ai[k + 1] - ai[k];

    1052:     tp = t + (*vj) * 4;
    1053:     while (nz--) {
    1054:       tp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3;
    1055:       tp[1] += v[4] * x0 + v[5] * x1 + v[6] * x2 + v[7] * x3;
    1056:       tp[2] += v[8] * x0 + v[9] * x1 + v[10] * x2 + v[11] * x3;
    1057:       tp[3] += v[12] * x0 + v[13] * x1 + v[14] * x2 + v[15] * x3;
    1058:       vj++;
    1059:       tp = t + (*vj) * 4;
    1060:       v += 16;
    1061:     }

    1063:     /* xk = inv(Dk)*(Dk*xk) */
    1064:     diag  = aa + k * 16; /* ptr to inv(Dk) */
    1065:     tp    = t + k * 4;
    1066:     tp[0] = diag[0] * x0 + diag[4] * x1 + diag[8] * x2 + diag[12] * x3;
    1067:     tp[1] = diag[1] * x0 + diag[5] * x1 + diag[9] * x2 + diag[13] * x3;
    1068:     tp[2] = diag[2] * x0 + diag[6] * x1 + diag[10] * x2 + diag[14] * x3;
    1069:     tp[3] = diag[3] * x0 + diag[7] * x1 + diag[11] * x2 + diag[15] * x3;
    1070:   }

    1072:   /* solve U*x = y by back substitution */
    1073:   for (k = mbs - 1; k >= 0; k--) {
    1074:     v  = aa + 16 * ai[k];
    1075:     vj = aj + ai[k];
    1076:     tp = t + k * 4;
    1077:     x0 = tp[0];
    1078:     x1 = tp[1];
    1079:     x2 = tp[2];
    1080:     x3 = tp[3]; /* xk */
    1081:     nz = ai[k + 1] - ai[k];

    1083:     tp = t + (*vj) * 4;
    1084:     while (nz--) {
    1085:       /* xk += U(k,:)*x(:) */
    1086:       x0 += v[0] * tp[0] + v[4] * tp[1] + v[8] * tp[2] + v[12] * tp[3];
    1087:       x1 += v[1] * tp[0] + v[5] * tp[1] + v[9] * tp[2] + v[13] * tp[3];
    1088:       x2 += v[2] * tp[0] + v[6] * tp[1] + v[10] * tp[2] + v[14] * tp[3];
    1089:       x3 += v[3] * tp[0] + v[7] * tp[1] + v[11] * tp[2] + v[15] * tp[3];
    1090:       vj++;
    1091:       tp = t + (*vj) * 4;
    1092:       v += 16;
    1093:     }
    1094:     tp         = t + k * 4;
    1095:     tp[0]      = x0;
    1096:     tp[1]      = x1;
    1097:     tp[2]      = x2;
    1098:     tp[3]      = x3;
    1099:     idx        = 4 * r[k];
    1100:     x[idx]     = x0;
    1101:     x[idx + 1] = x1;
    1102:     x[idx + 2] = x2;
    1103:     x[idx + 3] = x3;
    1104:   }

    1106:   PetscCall(ISRestoreIndices(isrow, &r));
    1107:   PetscCall(VecRestoreArrayRead(bb, &b));
    1108:   PetscCall(VecRestoreArray(xx, &x));
    1109:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    1110:   PetscFunctionReturn(PETSC_SUCCESS);
    1111: }

    1113: static PetscErrorCode MatForwardSolve_SeqSBAIJ_4_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    1114: {
    1115:   const MatScalar *v, *diag;
    1116:   PetscScalar     *xp, x0, x1, x2, x3;
    1117:   PetscInt         nz, k;
    1118:   const PetscInt  *vj;

    1120:   PetscFunctionBegin;
    1121:   for (k = 0; k < mbs; k++) {
    1122:     v  = aa + 16 * ai[k];
    1123:     xp = x + k * 4;
    1124:     x0 = xp[0];
    1125:     x1 = xp[1];
    1126:     x2 = xp[2];
    1127:     x3 = xp[3]; /* Dk*xk = k-th block of x */
    1128:     nz = ai[k + 1] - ai[k];
    1129:     vj = aj + ai[k];
    1130:     PetscPrefetchBlock(vj + nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    1131:     PetscPrefetchBlock(v + 16 * nz, 16 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    1132:     while (nz--) {
    1133:       xp = x + (*vj) * 4;
    1134:       /* x(:) += U(k,:)^T*(Dk*xk) */
    1135:       xp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2 + v[3] * x3;
    1136:       xp[1] += v[4] * x0 + v[5] * x1 + v[6] * x2 + v[7] * x3;
    1137:       xp[2] += v[8] * x0 + v[9] * x1 + v[10] * x2 + v[11] * x3;
    1138:       xp[3] += v[12] * x0 + v[13] * x1 + v[14] * x2 + v[15] * x3;
    1139:       vj++;
    1140:       v += 16;
    1141:     }
    1142:     /* xk = inv(Dk)*(Dk*xk) */
    1143:     diag  = aa + k * 16; /* ptr to inv(Dk) */
    1144:     xp    = x + k * 4;
    1145:     xp[0] = diag[0] * x0 + diag[4] * x1 + diag[8] * x2 + diag[12] * x3;
    1146:     xp[1] = diag[1] * x0 + diag[5] * x1 + diag[9] * x2 + diag[13] * x3;
    1147:     xp[2] = diag[2] * x0 + diag[6] * x1 + diag[10] * x2 + diag[14] * x3;
    1148:     xp[3] = diag[3] * x0 + diag[7] * x1 + diag[11] * x2 + diag[15] * x3;
    1149:   }
    1150:   PetscFunctionReturn(PETSC_SUCCESS);
    1151: }

    1153: static PetscErrorCode MatBackwardSolve_SeqSBAIJ_4_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    1154: {
    1155:   const MatScalar *v;
    1156:   PetscScalar     *xp, x0, x1, x2, x3;
    1157:   PetscInt         nz, k;
    1158:   const PetscInt  *vj;

    1160:   PetscFunctionBegin;
    1161:   for (k = mbs - 1; k >= 0; k--) {
    1162:     v  = aa + 16 * ai[k];
    1163:     xp = x + k * 4;
    1164:     x0 = xp[0];
    1165:     x1 = xp[1];
    1166:     x2 = xp[2];
    1167:     x3 = xp[3]; /* xk */
    1168:     nz = ai[k + 1] - ai[k];
    1169:     vj = aj + ai[k];
    1170:     PetscPrefetchBlock(vj - nz, nz, 0, PETSC_PREFETCH_HINT_NTA);          /* Indices for the next row (assumes same size as this one) */
    1171:     PetscPrefetchBlock(v - 16 * nz, 16 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    1172:     while (nz--) {
    1173:       xp = x + (*vj) * 4;
    1174:       /* xk += U(k,:)*x(:) */
    1175:       x0 += v[0] * xp[0] + v[4] * xp[1] + v[8] * xp[2] + v[12] * xp[3];
    1176:       x1 += v[1] * xp[0] + v[5] * xp[1] + v[9] * xp[2] + v[13] * xp[3];
    1177:       x2 += v[2] * xp[0] + v[6] * xp[1] + v[10] * xp[2] + v[14] * xp[3];
    1178:       x3 += v[3] * xp[0] + v[7] * xp[1] + v[11] * xp[2] + v[15] * xp[3];
    1179:       vj++;
    1180:       v += 16;
    1181:     }
    1182:     xp    = x + k * 4;
    1183:     xp[0] = x0;
    1184:     xp[1] = x1;
    1185:     xp[2] = x2;
    1186:     xp[3] = x3;
    1187:   }
    1188:   PetscFunctionReturn(PETSC_SUCCESS);
    1189: }

    1191: PetscErrorCode MatSolve_SeqSBAIJ_4_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1192: {
    1193:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1194:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1195:   const MatScalar   *aa = a->a;
    1196:   PetscScalar       *x;
    1197:   const PetscScalar *b;

    1199:   PetscFunctionBegin;
    1200:   PetscCall(VecGetArrayRead(bb, &b));
    1201:   PetscCall(VecGetArray(xx, &x));

    1203:   /* solve U^T * D * y = b by forward substitution */
    1204:   PetscCall(PetscArraycpy(x, b, 4 * mbs)); /* x <- b */
    1205:   PetscCall(MatForwardSolve_SeqSBAIJ_4_NaturalOrdering(ai, aj, aa, mbs, x));

    1207:   /* solve U*x = y by back substitution */
    1208:   PetscCall(MatBackwardSolve_SeqSBAIJ_4_NaturalOrdering(ai, aj, aa, mbs, x));
    1209:   PetscCall(VecRestoreArrayRead(bb, &b));
    1210:   PetscCall(VecRestoreArray(xx, &x));
    1211:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    1212:   PetscFunctionReturn(PETSC_SUCCESS);
    1213: }

    1215: PetscErrorCode MatForwardSolve_SeqSBAIJ_4_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1216: {
    1217:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1218:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1219:   const MatScalar   *aa = a->a;
    1220:   PetscScalar       *x;
    1221:   const PetscScalar *b;

    1223:   PetscFunctionBegin;
    1224:   PetscCall(VecGetArrayRead(bb, &b));
    1225:   PetscCall(VecGetArray(xx, &x));
    1226:   PetscCall(PetscArraycpy(x, b, 4 * mbs)); /* x <- b */
    1227:   PetscCall(MatForwardSolve_SeqSBAIJ_4_NaturalOrdering(ai, aj, aa, mbs, x));
    1228:   PetscCall(VecRestoreArrayRead(bb, &b));
    1229:   PetscCall(VecRestoreArray(xx, &x));
    1230:   PetscCall(PetscLogFlops(2.0 * a->bs2 * a->nz - A->rmap->bs * mbs));
    1231:   PetscFunctionReturn(PETSC_SUCCESS);
    1232: }

    1234: PetscErrorCode MatBackwardSolve_SeqSBAIJ_4_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1235: {
    1236:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1237:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1238:   const MatScalar   *aa = a->a;
    1239:   PetscScalar       *x;
    1240:   const PetscScalar *b;

    1242:   PetscFunctionBegin;
    1243:   PetscCall(VecGetArrayRead(bb, &b));
    1244:   PetscCall(VecGetArray(xx, &x));
    1245:   PetscCall(PetscArraycpy(x, b, 4 * mbs));
    1246:   PetscCall(MatBackwardSolve_SeqSBAIJ_4_NaturalOrdering(ai, aj, aa, mbs, x));
    1247:   PetscCall(VecRestoreArrayRead(bb, &b));
    1248:   PetscCall(VecRestoreArray(xx, &x));
    1249:   PetscCall(PetscLogFlops(2.0 * a->bs2 * (a->nz - mbs)));
    1250:   PetscFunctionReturn(PETSC_SUCCESS);
    1251: }

    1253: PetscErrorCode MatSolve_SeqSBAIJ_3_inplace(Mat A, Vec bb, Vec xx)
    1254: {
    1255:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1256:   IS                 isrow = a->row;
    1257:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1258:   const PetscInt    *r;
    1259:   PetscInt           nz, k, idx;
    1260:   const PetscInt    *vj;
    1261:   const MatScalar   *aa = a->a, *v, *diag;
    1262:   PetscScalar       *x, x0, x1, x2, *t, *tp;
    1263:   const PetscScalar *b;

    1265:   PetscFunctionBegin;
    1266:   PetscCall(VecGetArrayRead(bb, &b));
    1267:   PetscCall(VecGetArray(xx, &x));
    1268:   t = a->solve_work;
    1269:   PetscCall(ISGetIndices(isrow, &r));

    1271:   /* solve U^T * D * y = b by forward substitution */
    1272:   tp = t;
    1273:   for (k = 0; k < mbs; k++) { /* t <- perm(b) */
    1274:     idx   = 3 * r[k];
    1275:     tp[0] = b[idx];
    1276:     tp[1] = b[idx + 1];
    1277:     tp[2] = b[idx + 2];
    1278:     tp += 3;
    1279:   }

    1281:   for (k = 0; k < mbs; k++) {
    1282:     v  = aa + 9 * ai[k];
    1283:     vj = aj + ai[k];
    1284:     tp = t + k * 3;
    1285:     x0 = tp[0];
    1286:     x1 = tp[1];
    1287:     x2 = tp[2];
    1288:     nz = ai[k + 1] - ai[k];

    1290:     tp = t + (*vj) * 3;
    1291:     while (nz--) {
    1292:       tp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2;
    1293:       tp[1] += v[3] * x0 + v[4] * x1 + v[5] * x2;
    1294:       tp[2] += v[6] * x0 + v[7] * x1 + v[8] * x2;
    1295:       vj++;
    1296:       tp = t + (*vj) * 3;
    1297:       v += 9;
    1298:     }

    1300:     /* xk = inv(Dk)*(Dk*xk) */
    1301:     diag  = aa + k * 9; /* ptr to inv(Dk) */
    1302:     tp    = t + k * 3;
    1303:     tp[0] = diag[0] * x0 + diag[3] * x1 + diag[6] * x2;
    1304:     tp[1] = diag[1] * x0 + diag[4] * x1 + diag[7] * x2;
    1305:     tp[2] = diag[2] * x0 + diag[5] * x1 + diag[8] * x2;
    1306:   }

    1308:   /* solve U*x = y by back substitution */
    1309:   for (k = mbs - 1; k >= 0; k--) {
    1310:     v  = aa + 9 * ai[k];
    1311:     vj = aj + ai[k];
    1312:     tp = t + k * 3;
    1313:     x0 = tp[0];
    1314:     x1 = tp[1];
    1315:     x2 = tp[2]; /* xk */
    1316:     nz = ai[k + 1] - ai[k];

    1318:     tp = t + (*vj) * 3;
    1319:     while (nz--) {
    1320:       /* xk += U(k,:)*x(:) */
    1321:       x0 += v[0] * tp[0] + v[3] * tp[1] + v[6] * tp[2];
    1322:       x1 += v[1] * tp[0] + v[4] * tp[1] + v[7] * tp[2];
    1323:       x2 += v[2] * tp[0] + v[5] * tp[1] + v[8] * tp[2];
    1324:       vj++;
    1325:       tp = t + (*vj) * 3;
    1326:       v += 9;
    1327:     }
    1328:     tp         = t + k * 3;
    1329:     tp[0]      = x0;
    1330:     tp[1]      = x1;
    1331:     tp[2]      = x2;
    1332:     idx        = 3 * r[k];
    1333:     x[idx]     = x0;
    1334:     x[idx + 1] = x1;
    1335:     x[idx + 2] = x2;
    1336:   }

    1338:   PetscCall(ISRestoreIndices(isrow, &r));
    1339:   PetscCall(VecRestoreArrayRead(bb, &b));
    1340:   PetscCall(VecRestoreArray(xx, &x));
    1341:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    1342:   PetscFunctionReturn(PETSC_SUCCESS);
    1343: }

    1345: static PetscErrorCode MatForwardSolve_SeqSBAIJ_3_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    1346: {
    1347:   const MatScalar *v, *diag;
    1348:   PetscScalar     *xp, x0, x1, x2;
    1349:   PetscInt         nz, k;
    1350:   const PetscInt  *vj;

    1352:   PetscFunctionBegin;
    1353:   for (k = 0; k < mbs; k++) {
    1354:     v  = aa + 9 * ai[k];
    1355:     xp = x + k * 3;
    1356:     x0 = xp[0];
    1357:     x1 = xp[1];
    1358:     x2 = xp[2]; /* Dk*xk = k-th block of x */
    1359:     nz = ai[k + 1] - ai[k];
    1360:     vj = aj + ai[k];
    1361:     PetscPrefetchBlock(vj + nz, nz, 0, PETSC_PREFETCH_HINT_NTA);        /* Indices for the next row (assumes same size as this one) */
    1362:     PetscPrefetchBlock(v + 9 * nz, 9 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    1363:     while (nz--) {
    1364:       xp = x + (*vj) * 3;
    1365:       /* x(:) += U(k,:)^T*(Dk*xk) */
    1366:       xp[0] += v[0] * x0 + v[1] * x1 + v[2] * x2;
    1367:       xp[1] += v[3] * x0 + v[4] * x1 + v[5] * x2;
    1368:       xp[2] += v[6] * x0 + v[7] * x1 + v[8] * x2;
    1369:       vj++;
    1370:       v += 9;
    1371:     }
    1372:     /* xk = inv(Dk)*(Dk*xk) */
    1373:     diag  = aa + k * 9; /* ptr to inv(Dk) */
    1374:     xp    = x + k * 3;
    1375:     xp[0] = diag[0] * x0 + diag[3] * x1 + diag[6] * x2;
    1376:     xp[1] = diag[1] * x0 + diag[4] * x1 + diag[7] * x2;
    1377:     xp[2] = diag[2] * x0 + diag[5] * x1 + diag[8] * x2;
    1378:   }
    1379:   PetscFunctionReturn(PETSC_SUCCESS);
    1380: }

    1382: static PetscErrorCode MatBackwardSolve_SeqSBAIJ_3_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    1383: {
    1384:   const MatScalar *v;
    1385:   PetscScalar     *xp, x0, x1, x2;
    1386:   PetscInt         nz, k;
    1387:   const PetscInt  *vj;

    1389:   PetscFunctionBegin;
    1390:   for (k = mbs - 1; k >= 0; k--) {
    1391:     v  = aa + 9 * ai[k];
    1392:     xp = x + k * 3;
    1393:     x0 = xp[0];
    1394:     x1 = xp[1];
    1395:     x2 = xp[2]; /* xk */
    1396:     nz = ai[k + 1] - ai[k];
    1397:     vj = aj + ai[k];
    1398:     PetscPrefetchBlock(vj - nz, nz, 0, PETSC_PREFETCH_HINT_NTA);        /* Indices for the next row (assumes same size as this one) */
    1399:     PetscPrefetchBlock(v - 9 * nz, 9 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    1400:     while (nz--) {
    1401:       xp = x + (*vj) * 3;
    1402:       /* xk += U(k,:)*x(:) */
    1403:       x0 += v[0] * xp[0] + v[3] * xp[1] + v[6] * xp[2];
    1404:       x1 += v[1] * xp[0] + v[4] * xp[1] + v[7] * xp[2];
    1405:       x2 += v[2] * xp[0] + v[5] * xp[1] + v[8] * xp[2];
    1406:       vj++;
    1407:       v += 9;
    1408:     }
    1409:     xp    = x + k * 3;
    1410:     xp[0] = x0;
    1411:     xp[1] = x1;
    1412:     xp[2] = x2;
    1413:   }
    1414:   PetscFunctionReturn(PETSC_SUCCESS);
    1415: }

    1417: PetscErrorCode MatSolve_SeqSBAIJ_3_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1418: {
    1419:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1420:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1421:   const MatScalar   *aa = a->a;
    1422:   PetscScalar       *x;
    1423:   const PetscScalar *b;

    1425:   PetscFunctionBegin;
    1426:   PetscCall(VecGetArrayRead(bb, &b));
    1427:   PetscCall(VecGetArray(xx, &x));

    1429:   /* solve U^T * D * y = b by forward substitution */
    1430:   PetscCall(PetscArraycpy(x, b, 3 * mbs));
    1431:   PetscCall(MatForwardSolve_SeqSBAIJ_3_NaturalOrdering(ai, aj, aa, mbs, x));

    1433:   /* solve U*x = y by back substitution */
    1434:   PetscCall(MatBackwardSolve_SeqSBAIJ_3_NaturalOrdering(ai, aj, aa, mbs, x));

    1436:   PetscCall(VecRestoreArrayRead(bb, &b));
    1437:   PetscCall(VecRestoreArray(xx, &x));
    1438:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    1439:   PetscFunctionReturn(PETSC_SUCCESS);
    1440: }

    1442: PetscErrorCode MatForwardSolve_SeqSBAIJ_3_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1443: {
    1444:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1445:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1446:   const MatScalar   *aa = a->a;
    1447:   PetscScalar       *x;
    1448:   const PetscScalar *b;

    1450:   PetscFunctionBegin;
    1451:   PetscCall(VecGetArrayRead(bb, &b));
    1452:   PetscCall(VecGetArray(xx, &x));
    1453:   PetscCall(PetscArraycpy(x, b, 3 * mbs));
    1454:   PetscCall(MatForwardSolve_SeqSBAIJ_3_NaturalOrdering(ai, aj, aa, mbs, x));
    1455:   PetscCall(VecRestoreArrayRead(bb, &b));
    1456:   PetscCall(VecRestoreArray(xx, &x));
    1457:   PetscCall(PetscLogFlops(2.0 * a->bs2 * a->nz - A->rmap->bs * mbs));
    1458:   PetscFunctionReturn(PETSC_SUCCESS);
    1459: }

    1461: PetscErrorCode MatBackwardSolve_SeqSBAIJ_3_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1462: {
    1463:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1464:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1465:   const MatScalar   *aa = a->a;
    1466:   PetscScalar       *x;
    1467:   const PetscScalar *b;

    1469:   PetscFunctionBegin;
    1470:   PetscCall(VecGetArrayRead(bb, &b));
    1471:   PetscCall(VecGetArray(xx, &x));
    1472:   PetscCall(PetscArraycpy(x, b, 3 * mbs));
    1473:   PetscCall(MatBackwardSolve_SeqSBAIJ_3_NaturalOrdering(ai, aj, aa, mbs, x));
    1474:   PetscCall(VecRestoreArrayRead(bb, &b));
    1475:   PetscCall(VecRestoreArray(xx, &x));
    1476:   PetscCall(PetscLogFlops(2.0 * a->bs2 * (a->nz - mbs)));
    1477:   PetscFunctionReturn(PETSC_SUCCESS);
    1478: }

    1480: PetscErrorCode MatSolve_SeqSBAIJ_2_inplace(Mat A, Vec bb, Vec xx)
    1481: {
    1482:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1483:   IS                 isrow = a->row;
    1484:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1485:   const PetscInt    *r, *vj;
    1486:   PetscInt           nz, k, k2, idx;
    1487:   const MatScalar   *aa = a->a, *v, *diag;
    1488:   PetscScalar       *x, x0, x1, *t;
    1489:   const PetscScalar *b;

    1491:   PetscFunctionBegin;
    1492:   PetscCall(VecGetArrayRead(bb, &b));
    1493:   PetscCall(VecGetArray(xx, &x));
    1494:   t = a->solve_work;
    1495:   PetscCall(ISGetIndices(isrow, &r));

    1497:   /* solve U^T * D * y = perm(b) by forward substitution */
    1498:   for (k = 0; k < mbs; k++) { /* t <- perm(b) */
    1499:     idx          = 2 * r[k];
    1500:     t[k * 2]     = b[idx];
    1501:     t[k * 2 + 1] = b[idx + 1];
    1502:   }
    1503:   for (k = 0; k < mbs; k++) {
    1504:     v  = aa + 4 * ai[k];
    1505:     vj = aj + ai[k];
    1506:     k2 = k * 2;
    1507:     x0 = t[k2];
    1508:     x1 = t[k2 + 1];
    1509:     nz = ai[k + 1] - ai[k];
    1510:     while (nz--) {
    1511:       t[(*vj) * 2] += v[0] * x0 + v[1] * x1;
    1512:       t[(*vj) * 2 + 1] += v[2] * x0 + v[3] * x1;
    1513:       vj++;
    1514:       v += 4;
    1515:     }
    1516:     diag      = aa + k * 4; /* ptr to inv(Dk) */
    1517:     t[k2]     = diag[0] * x0 + diag[2] * x1;
    1518:     t[k2 + 1] = diag[1] * x0 + diag[3] * x1;
    1519:   }

    1521:   /* solve U*x = y by back substitution */
    1522:   for (k = mbs - 1; k >= 0; k--) {
    1523:     v  = aa + 4 * ai[k];
    1524:     vj = aj + ai[k];
    1525:     k2 = k * 2;
    1526:     x0 = t[k2];
    1527:     x1 = t[k2 + 1];
    1528:     nz = ai[k + 1] - ai[k];
    1529:     while (nz--) {
    1530:       x0 += v[0] * t[(*vj) * 2] + v[2] * t[(*vj) * 2 + 1];
    1531:       x1 += v[1] * t[(*vj) * 2] + v[3] * t[(*vj) * 2 + 1];
    1532:       vj++;
    1533:       v += 4;
    1534:     }
    1535:     t[k2]      = x0;
    1536:     t[k2 + 1]  = x1;
    1537:     idx        = 2 * r[k];
    1538:     x[idx]     = x0;
    1539:     x[idx + 1] = x1;
    1540:   }

    1542:   PetscCall(ISRestoreIndices(isrow, &r));
    1543:   PetscCall(VecRestoreArrayRead(bb, &b));
    1544:   PetscCall(VecRestoreArray(xx, &x));
    1545:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    1546:   PetscFunctionReturn(PETSC_SUCCESS);
    1547: }

    1549: static PetscErrorCode MatForwardSolve_SeqSBAIJ_2_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    1550: {
    1551:   const MatScalar *v, *diag;
    1552:   PetscScalar      x0, x1;
    1553:   PetscInt         nz, k, k2;
    1554:   const PetscInt  *vj;

    1556:   PetscFunctionBegin;
    1557:   for (k = 0; k < mbs; k++) {
    1558:     v  = aa + 4 * ai[k];
    1559:     vj = aj + ai[k];
    1560:     k2 = k * 2;
    1561:     x0 = x[k2];
    1562:     x1 = x[k2 + 1]; /* Dk*xk = k-th block of x */
    1563:     nz = ai[k + 1] - ai[k];
    1564:     PetscPrefetchBlock(vj + nz, nz, 0, PETSC_PREFETCH_HINT_NTA);        /* Indices for the next row (assumes same size as this one) */
    1565:     PetscPrefetchBlock(v + 4 * nz, 4 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    1566:     while (nz--) {
    1567:       /* x(:) += U(k,:)^T*(Dk*xk) */
    1568:       x[(*vj) * 2] += v[0] * x0 + v[1] * x1;
    1569:       x[(*vj) * 2 + 1] += v[2] * x0 + v[3] * x1;
    1570:       vj++;
    1571:       v += 4;
    1572:     }
    1573:     /* xk = inv(Dk)*(Dk*xk) */
    1574:     diag      = aa + k * 4; /* ptr to inv(Dk) */
    1575:     x[k2]     = diag[0] * x0 + diag[2] * x1;
    1576:     x[k2 + 1] = diag[1] * x0 + diag[3] * x1;
    1577:   }
    1578:   PetscFunctionReturn(PETSC_SUCCESS);
    1579: }

    1581: static PetscErrorCode MatBackwardSolve_SeqSBAIJ_2_NaturalOrdering(const PetscInt *ai, const PetscInt *aj, const MatScalar *aa, PetscInt mbs, PetscScalar *x)
    1582: {
    1583:   const MatScalar *v;
    1584:   PetscScalar      x0, x1;
    1585:   PetscInt         nz, k, k2;
    1586:   const PetscInt  *vj;

    1588:   PetscFunctionBegin;
    1589:   for (k = mbs - 1; k >= 0; k--) {
    1590:     v  = aa + 4 * ai[k];
    1591:     vj = aj + ai[k];
    1592:     k2 = k * 2;
    1593:     x0 = x[k2];
    1594:     x1 = x[k2 + 1]; /* xk */
    1595:     nz = ai[k + 1] - ai[k];
    1596:     PetscPrefetchBlock(vj - nz, nz, 0, PETSC_PREFETCH_HINT_NTA);        /* Indices for the next row (assumes same size as this one) */
    1597:     PetscPrefetchBlock(v - 4 * nz, 4 * nz, 0, PETSC_PREFETCH_HINT_NTA); /* Entries for the next row */
    1598:     while (nz--) {
    1599:       /* xk += U(k,:)*x(:) */
    1600:       x0 += v[0] * x[(*vj) * 2] + v[2] * x[(*vj) * 2 + 1];
    1601:       x1 += v[1] * x[(*vj) * 2] + v[3] * x[(*vj) * 2 + 1];
    1602:       vj++;
    1603:       v += 4;
    1604:     }
    1605:     x[k2]     = x0;
    1606:     x[k2 + 1] = x1;
    1607:   }
    1608:   PetscFunctionReturn(PETSC_SUCCESS);
    1609: }

    1611: PetscErrorCode MatSolve_SeqSBAIJ_2_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1612: {
    1613:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1614:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1615:   const MatScalar   *aa = a->a;
    1616:   PetscScalar       *x;
    1617:   const PetscScalar *b;

    1619:   PetscFunctionBegin;
    1620:   PetscCall(VecGetArrayRead(bb, &b));
    1621:   PetscCall(VecGetArray(xx, &x));

    1623:   /* solve U^T * D * y = b by forward substitution */
    1624:   PetscCall(PetscArraycpy(x, b, 2 * mbs));
    1625:   PetscCall(MatForwardSolve_SeqSBAIJ_2_NaturalOrdering(ai, aj, aa, mbs, x));

    1627:   /* solve U*x = y by back substitution */
    1628:   PetscCall(MatBackwardSolve_SeqSBAIJ_2_NaturalOrdering(ai, aj, aa, mbs, x));

    1630:   PetscCall(VecRestoreArrayRead(bb, &b));
    1631:   PetscCall(VecRestoreArray(xx, &x));
    1632:   PetscCall(PetscLogFlops(4.0 * a->bs2 * a->nz - (A->rmap->bs + 2.0 * a->bs2) * mbs));
    1633:   PetscFunctionReturn(PETSC_SUCCESS);
    1634: }

    1636: PetscErrorCode MatForwardSolve_SeqSBAIJ_2_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1637: {
    1638:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1639:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1640:   const MatScalar   *aa = a->a;
    1641:   PetscScalar       *x;
    1642:   const PetscScalar *b;

    1644:   PetscFunctionBegin;
    1645:   PetscCall(VecGetArrayRead(bb, &b));
    1646:   PetscCall(VecGetArray(xx, &x));
    1647:   PetscCall(PetscArraycpy(x, b, 2 * mbs));
    1648:   PetscCall(MatForwardSolve_SeqSBAIJ_2_NaturalOrdering(ai, aj, aa, mbs, x));
    1649:   PetscCall(VecRestoreArrayRead(bb, &b));
    1650:   PetscCall(VecRestoreArray(xx, &x));
    1651:   PetscCall(PetscLogFlops(2.0 * a->bs2 * a->nz - A->rmap->bs * mbs));
    1652:   PetscFunctionReturn(PETSC_SUCCESS);
    1653: }

    1655: PetscErrorCode MatBackwardSolve_SeqSBAIJ_2_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    1656: {
    1657:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    1658:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j;
    1659:   const MatScalar   *aa = a->a;
    1660:   PetscScalar       *x;
    1661:   const PetscScalar *b;

    1663:   PetscFunctionBegin;
    1664:   PetscCall(VecGetArrayRead(bb, &b));
    1665:   PetscCall(VecGetArray(xx, &x));
    1666:   PetscCall(PetscArraycpy(x, b, 2 * mbs));
    1667:   PetscCall(MatBackwardSolve_SeqSBAIJ_2_NaturalOrdering(ai, aj, aa, mbs, x));
    1668:   PetscCall(VecRestoreArrayRead(bb, &b));
    1669:   PetscCall(VecRestoreArray(xx, &x));
    1670:   PetscCall(PetscLogFlops(2.0 * a->bs2 * (a->nz - mbs)));
    1671:   PetscFunctionReturn(PETSC_SUCCESS);
    1672: }

    1674: PetscErrorCode MatSolve_SeqSBAIJ_1(Mat A, Vec bb, Vec xx)
    1675: {
    1676:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1677:   IS                 isrow = a->row;
    1678:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *rp, *vj, *adiag = a->diag;
    1679:   const MatScalar   *aa = a->a, *v;
    1680:   const PetscScalar *b;
    1681:   PetscScalar       *x, xk, *t;
    1682:   PetscInt           nz, k, j;

    1684:   PetscFunctionBegin;
    1685:   PetscCall(VecGetArrayRead(bb, &b));
    1686:   PetscCall(VecGetArray(xx, &x));
    1687:   t = a->solve_work;
    1688:   PetscCall(ISGetIndices(isrow, &rp));

    1690:   /* solve U^T*D*y = perm(b) by forward substitution */
    1691:   for (k = 0; k < mbs; k++) t[k] = b[rp[k]];
    1692:   for (k = 0; k < mbs; k++) {
    1693:     v  = aa + ai[k];
    1694:     vj = aj + ai[k];
    1695:     xk = t[k];
    1696:     nz = ai[k + 1] - ai[k] - 1;
    1697:     for (j = 0; j < nz; j++) t[vj[j]] += v[j] * xk;
    1698:     t[k] = xk * v[nz]; /* v[nz] = 1/D(k) */
    1699:   }

    1701:   /* solve U*perm(x) = y by back substitution */
    1702:   for (k = mbs - 1; k >= 0; k--) {
    1703:     v  = aa + adiag[k] - 1;
    1704:     vj = aj + adiag[k] - 1;
    1705:     nz = ai[k + 1] - ai[k] - 1;
    1706:     for (j = 0; j < nz; j++) t[k] += v[-j] * t[vj[-j]];
    1707:     x[rp[k]] = t[k];
    1708:   }

    1710:   PetscCall(ISRestoreIndices(isrow, &rp));
    1711:   PetscCall(VecRestoreArrayRead(bb, &b));
    1712:   PetscCall(VecRestoreArray(xx, &x));
    1713:   PetscCall(PetscLogFlops(4.0 * a->nz - 3.0 * mbs));
    1714:   PetscFunctionReturn(PETSC_SUCCESS);
    1715: }

    1717: PetscErrorCode MatSolve_SeqSBAIJ_1_inplace(Mat A, Vec bb, Vec xx)
    1718: {
    1719:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1720:   IS                 isrow = a->row;
    1721:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *rp, *vj;
    1722:   const MatScalar   *aa = a->a, *v;
    1723:   PetscScalar       *x, xk, *t;
    1724:   const PetscScalar *b;
    1725:   PetscInt           nz, k;

    1727:   PetscFunctionBegin;
    1728:   PetscCall(VecGetArrayRead(bb, &b));
    1729:   PetscCall(VecGetArray(xx, &x));
    1730:   t = a->solve_work;
    1731:   PetscCall(ISGetIndices(isrow, &rp));

    1733:   /* solve U^T*D*y = perm(b) by forward substitution */
    1734:   for (k = 0; k < mbs; k++) t[k] = b[rp[k]];
    1735:   for (k = 0; k < mbs; k++) {
    1736:     v  = aa + ai[k] + 1;
    1737:     vj = aj + ai[k] + 1;
    1738:     xk = t[k];
    1739:     nz = ai[k + 1] - ai[k] - 1;
    1740:     while (nz--) t[*vj++] += (*v++) * xk;
    1741:     t[k] = xk * aa[ai[k]]; /* aa[k] = 1/D(k) */
    1742:   }

    1744:   /* solve U*perm(x) = y by back substitution */
    1745:   for (k = mbs - 1; k >= 0; k--) {
    1746:     v  = aa + ai[k] + 1;
    1747:     vj = aj + ai[k] + 1;
    1748:     nz = ai[k + 1] - ai[k] - 1;
    1749:     while (nz--) t[k] += (*v++) * t[*vj++];
    1750:     x[rp[k]] = t[k];
    1751:   }

    1753:   PetscCall(ISRestoreIndices(isrow, &rp));
    1754:   PetscCall(VecRestoreArrayRead(bb, &b));
    1755:   PetscCall(VecRestoreArray(xx, &x));
    1756:   PetscCall(PetscLogFlops(4.0 * a->nz - 3 * mbs));
    1757:   PetscFunctionReturn(PETSC_SUCCESS);
    1758: }

    1760: PetscErrorCode MatForwardSolve_SeqSBAIJ_1(Mat A, Vec bb, Vec xx)
    1761: {
    1762:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1763:   IS                 isrow = a->row;
    1764:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *rp, *vj, *adiag = a->diag;
    1765:   const MatScalar   *aa = a->a, *v;
    1766:   PetscReal          diagk;
    1767:   PetscScalar       *x, xk;
    1768:   const PetscScalar *b;
    1769:   PetscInt           nz, k;

    1771:   PetscFunctionBegin;
    1772:   /* solve U^T*D^(1/2)*x = perm(b) by forward substitution */
    1773:   PetscCall(VecGetArrayRead(bb, &b));
    1774:   PetscCall(VecGetArray(xx, &x));
    1775:   PetscCall(ISGetIndices(isrow, &rp));

    1777:   for (k = 0; k < mbs; k++) x[k] = b[rp[k]];
    1778:   for (k = 0; k < mbs; k++) {
    1779:     v  = aa + ai[k];
    1780:     vj = aj + ai[k];
    1781:     xk = x[k];
    1782:     nz = ai[k + 1] - ai[k] - 1;
    1783:     while (nz--) x[*vj++] += (*v++) * xk;

    1785:     diagk = PetscRealPart(aa[adiag[k]]); /* note: aa[diag[k]] = 1/D(k) */
    1786:     PetscCheck(!PetscImaginaryPart(aa[adiag[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal must be real and nonnegative");
    1787:     x[k] = xk * PetscSqrtReal(diagk);
    1788:   }
    1789:   PetscCall(ISRestoreIndices(isrow, &rp));
    1790:   PetscCall(VecRestoreArrayRead(bb, &b));
    1791:   PetscCall(VecRestoreArray(xx, &x));
    1792:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    1793:   PetscFunctionReturn(PETSC_SUCCESS);
    1794: }

    1796: PetscErrorCode MatForwardSolve_SeqSBAIJ_1_inplace(Mat A, Vec bb, Vec xx)
    1797: {
    1798:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1799:   IS                 isrow = a->row;
    1800:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *rp, *vj;
    1801:   const MatScalar   *aa = a->a, *v;
    1802:   PetscReal          diagk;
    1803:   PetscScalar       *x, xk;
    1804:   const PetscScalar *b;
    1805:   PetscInt           nz, k;

    1807:   PetscFunctionBegin;
    1808:   /* solve U^T*D^(1/2)*x = perm(b) by forward substitution */
    1809:   PetscCall(VecGetArrayRead(bb, &b));
    1810:   PetscCall(VecGetArray(xx, &x));
    1811:   PetscCall(ISGetIndices(isrow, &rp));

    1813:   for (k = 0; k < mbs; k++) x[k] = b[rp[k]];
    1814:   for (k = 0; k < mbs; k++) {
    1815:     v  = aa + ai[k] + 1;
    1816:     vj = aj + ai[k] + 1;
    1817:     xk = x[k];
    1818:     nz = ai[k + 1] - ai[k] - 1;
    1819:     while (nz--) x[*vj++] += (*v++) * xk;

    1821:     diagk = PetscRealPart(aa[ai[k]]); /* note: aa[diag[k]] = 1/D(k) */
    1822:     PetscCheck(!PetscImaginaryPart(aa[ai[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal must be real and nonnegative");
    1823:     x[k] = xk * PetscSqrtReal(diagk);
    1824:   }
    1825:   PetscCall(ISRestoreIndices(isrow, &rp));
    1826:   PetscCall(VecRestoreArrayRead(bb, &b));
    1827:   PetscCall(VecRestoreArray(xx, &x));
    1828:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    1829:   PetscFunctionReturn(PETSC_SUCCESS);
    1830: }

    1832: PetscErrorCode MatBackwardSolve_SeqSBAIJ_1(Mat A, Vec bb, Vec xx)
    1833: {
    1834:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1835:   IS                 isrow = a->row;
    1836:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *rp, *vj, *adiag = a->diag;
    1837:   const MatScalar   *aa = a->a, *v;
    1838:   PetscReal          diagk;
    1839:   PetscScalar       *x, *t;
    1840:   const PetscScalar *b;
    1841:   PetscInt           nz, k;

    1843:   PetscFunctionBegin;
    1844:   /* solve D^(1/2)*U*perm(x) = b by back substitution */
    1845:   PetscCall(VecGetArrayRead(bb, &b));
    1846:   PetscCall(VecGetArray(xx, &x));
    1847:   t = a->solve_work;
    1848:   PetscCall(ISGetIndices(isrow, &rp));

    1850:   for (k = mbs - 1; k >= 0; k--) {
    1851:     v     = aa + ai[k];
    1852:     vj    = aj + ai[k];
    1853:     diagk = PetscRealPart(aa[adiag[k]]);
    1854:     PetscCheck(!PetscImaginaryPart(aa[adiag[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal must be real and nonnegative");
    1855:     t[k] = b[k] * PetscSqrtReal(diagk);
    1856:     nz   = ai[k + 1] - ai[k] - 1;
    1857:     while (nz--) t[k] += (*v++) * t[*vj++];
    1858:     x[rp[k]] = t[k];
    1859:   }
    1860:   PetscCall(ISRestoreIndices(isrow, &rp));
    1861:   PetscCall(VecRestoreArrayRead(bb, &b));
    1862:   PetscCall(VecRestoreArray(xx, &x));
    1863:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    1864:   PetscFunctionReturn(PETSC_SUCCESS);
    1865: }

    1867: PetscErrorCode MatBackwardSolve_SeqSBAIJ_1_inplace(Mat A, Vec bb, Vec xx)
    1868: {
    1869:   Mat_SeqSBAIJ      *a     = (Mat_SeqSBAIJ *)A->data;
    1870:   IS                 isrow = a->row;
    1871:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *rp, *vj;
    1872:   const MatScalar   *aa = a->a, *v;
    1873:   PetscReal          diagk;
    1874:   PetscScalar       *x, *t;
    1875:   const PetscScalar *b;
    1876:   PetscInt           nz, k;

    1878:   PetscFunctionBegin;
    1879:   /* solve D^(1/2)*U*perm(x) = b by back substitution */
    1880:   PetscCall(VecGetArrayRead(bb, &b));
    1881:   PetscCall(VecGetArray(xx, &x));
    1882:   t = a->solve_work;
    1883:   PetscCall(ISGetIndices(isrow, &rp));

    1885:   for (k = mbs - 1; k >= 0; k--) {
    1886:     v     = aa + ai[k] + 1;
    1887:     vj    = aj + ai[k] + 1;
    1888:     diagk = PetscRealPart(aa[ai[k]]);
    1889:     PetscCheck(!PetscImaginaryPart(aa[ai[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal must be real and nonnegative");
    1890:     t[k] = b[k] * PetscSqrtReal(diagk);
    1891:     nz   = ai[k + 1] - ai[k] - 1;
    1892:     while (nz--) t[k] += (*v++) * t[*vj++];
    1893:     x[rp[k]] = t[k];
    1894:   }
    1895:   PetscCall(ISRestoreIndices(isrow, &rp));
    1896:   PetscCall(VecRestoreArrayRead(bb, &b));
    1897:   PetscCall(VecRestoreArray(xx, &x));
    1898:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    1899:   PetscFunctionReturn(PETSC_SUCCESS);
    1900: }

    1902: PetscErrorCode MatSolves_SeqSBAIJ_1(Mat A, Vecs bb, Vecs xx)
    1903: {
    1904:   Mat_SeqSBAIJ *a = (Mat_SeqSBAIJ *)A->data;

    1906:   PetscFunctionBegin;
    1907:   if (A->rmap->bs == 1) {
    1908:     PetscCall(MatSolve_SeqSBAIJ_1(A, bb->v, xx->v));
    1909:   } else {
    1910:     IS                 isrow = a->row;
    1911:     const PetscInt    *vj, mbs = a->mbs, *ai = a->i, *aj = a->j, *rp;
    1912:     const MatScalar   *aa = a->a, *v;
    1913:     PetscScalar       *x, *t;
    1914:     const PetscScalar *b;
    1915:     PetscInt           nz, k, n, i, j;

    1917:     if (bb->n > a->solves_work_n) {
    1918:       PetscCall(PetscFree(a->solves_work));
    1919:       PetscCall(PetscMalloc1(bb->n * A->rmap->N, &a->solves_work));
    1920:       a->solves_work_n = bb->n;
    1921:     }
    1922:     n = bb->n;
    1923:     PetscCall(VecGetArrayRead(bb->v, &b));
    1924:     PetscCall(VecGetArray(xx->v, &x));
    1925:     t = a->solves_work;

    1927:     PetscCall(ISGetIndices(isrow, &rp));

    1929:     /* solve U^T*D*y = perm(b) by forward substitution */
    1930:     for (k = 0; k < mbs; k++) {
    1931:       for (i = 0; i < n; i++) t[n * k + i] = b[rp[k] + i * mbs]; /* values are stored interlaced in t */
    1932:     }
    1933:     for (k = 0; k < mbs; k++) {
    1934:       v  = aa + ai[k];
    1935:       vj = aj + ai[k];
    1936:       nz = ai[k + 1] - ai[k] - 1;
    1937:       for (j = 0; j < nz; j++) {
    1938:         for (i = 0; i < n; i++) t[n * (*vj) + i] += (*v) * t[n * k + i];
    1939:         v++;
    1940:         vj++;
    1941:       }
    1942:       for (i = 0; i < n; i++) t[n * k + i] *= aa[nz]; /* note: aa[nz] = 1/D(k) */
    1943:     }

    1945:     /* solve U*perm(x) = y by back substitution */
    1946:     for (k = mbs - 1; k >= 0; k--) {
    1947:       v  = aa + ai[k] - 1;
    1948:       vj = aj + ai[k] - 1;
    1949:       nz = ai[k + 1] - ai[k] - 1;
    1950:       for (j = 0; j < nz; j++) {
    1951:         for (i = 0; i < n; i++) t[n * k + i] += (*v) * t[n * (*vj) + i];
    1952:         v++;
    1953:         vj++;
    1954:       }
    1955:       for (i = 0; i < n; i++) x[rp[k] + i * mbs] = t[n * k + i];
    1956:     }

    1958:     PetscCall(ISRestoreIndices(isrow, &rp));
    1959:     PetscCall(VecRestoreArrayRead(bb->v, &b));
    1960:     PetscCall(VecRestoreArray(xx->v, &x));
    1961:     PetscCall(PetscLogFlops(bb->n * (4.0 * a->nz - 3.0 * mbs)));
    1962:   }
    1963:   PetscFunctionReturn(PETSC_SUCCESS);
    1964: }

    1966: PetscErrorCode MatSolves_SeqSBAIJ_1_inplace(Mat A, Vecs bb, Vecs xx)
    1967: {
    1968:   Mat_SeqSBAIJ *a = (Mat_SeqSBAIJ *)A->data;

    1970:   PetscFunctionBegin;
    1971:   if (A->rmap->bs == 1) {
    1972:     PetscCall(MatSolve_SeqSBAIJ_1_inplace(A, bb->v, xx->v));
    1973:   } else {
    1974:     IS                 isrow = a->row;
    1975:     const PetscInt    *vj, mbs = a->mbs, *ai = a->i, *aj = a->j, *rp;
    1976:     const MatScalar   *aa = a->a, *v;
    1977:     PetscScalar       *x, *t;
    1978:     const PetscScalar *b;
    1979:     PetscInt           nz, k, n, i;

    1981:     if (bb->n > a->solves_work_n) {
    1982:       PetscCall(PetscFree(a->solves_work));
    1983:       PetscCall(PetscMalloc1(bb->n * A->rmap->N, &a->solves_work));
    1984:       a->solves_work_n = bb->n;
    1985:     }
    1986:     n = bb->n;
    1987:     PetscCall(VecGetArrayRead(bb->v, &b));
    1988:     PetscCall(VecGetArray(xx->v, &x));
    1989:     t = a->solves_work;

    1991:     PetscCall(ISGetIndices(isrow, &rp));

    1993:     /* solve U^T*D*y = perm(b) by forward substitution */
    1994:     for (k = 0; k < mbs; k++) {
    1995:       for (i = 0; i < n; i++) t[n * k + i] = b[rp[k] + i * mbs]; /* values are stored interlaced in t */
    1996:     }
    1997:     for (k = 0; k < mbs; k++) {
    1998:       v  = aa + ai[k];
    1999:       vj = aj + ai[k];
    2000:       nz = ai[k + 1] - ai[k];
    2001:       while (nz--) {
    2002:         for (i = 0; i < n; i++) t[n * (*vj) + i] += (*v) * t[n * k + i];
    2003:         v++;
    2004:         vj++;
    2005:       }
    2006:       for (i = 0; i < n; i++) t[n * k + i] *= aa[k]; /* note: aa[k] = 1/D(k) */
    2007:     }

    2009:     /* solve U*perm(x) = y by back substitution */
    2010:     for (k = mbs - 1; k >= 0; k--) {
    2011:       v  = aa + ai[k];
    2012:       vj = aj + ai[k];
    2013:       nz = ai[k + 1] - ai[k];
    2014:       while (nz--) {
    2015:         for (i = 0; i < n; i++) t[n * k + i] += (*v) * t[n * (*vj) + i];
    2016:         v++;
    2017:         vj++;
    2018:       }
    2019:       for (i = 0; i < n; i++) x[rp[k] + i * mbs] = t[n * k + i];
    2020:     }

    2022:     PetscCall(ISRestoreIndices(isrow, &rp));
    2023:     PetscCall(VecRestoreArrayRead(bb->v, &b));
    2024:     PetscCall(VecRestoreArray(xx->v, &x));
    2025:     PetscCall(PetscLogFlops(bb->n * (4.0 * a->nz - 3.0 * mbs)));
    2026:   }
    2027:   PetscFunctionReturn(PETSC_SUCCESS);
    2028: }

    2030: PetscErrorCode MatSolve_SeqSBAIJ_1_NaturalOrdering(Mat A, Vec bb, Vec xx)
    2031: {
    2032:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    2033:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *vj, *adiag = a->diag;
    2034:   const MatScalar   *aa = a->a, *v;
    2035:   const PetscScalar *b;
    2036:   PetscScalar       *x, xi;
    2037:   PetscInt           nz, i, j;

    2039:   PetscFunctionBegin;
    2040:   PetscCall(VecGetArrayRead(bb, &b));
    2041:   PetscCall(VecGetArray(xx, &x));
    2042:   /* solve U^T*D*y = b by forward substitution */
    2043:   PetscCall(PetscArraycpy(x, b, mbs));
    2044:   for (i = 0; i < mbs; i++) {
    2045:     v  = aa + ai[i];
    2046:     vj = aj + ai[i];
    2047:     xi = x[i];
    2048:     nz = ai[i + 1] - ai[i] - 1; /* exclude diag[i] */
    2049:     for (j = 0; j < nz; j++) x[vj[j]] += v[j] * xi;
    2050:     x[i] = xi * v[nz]; /* v[nz] = aa[diag[i]] = 1/D(i) */
    2051:   }
    2052:   /* solve U*x = y by backward substitution */
    2053:   for (i = mbs - 2; i >= 0; i--) {
    2054:     xi = x[i];
    2055:     v  = aa + adiag[i] - 1; /* end of row i, excluding diag */
    2056:     vj = aj + adiag[i] - 1;
    2057:     nz = ai[i + 1] - ai[i] - 1;
    2058:     for (j = 0; j < nz; j++) xi += v[-j] * x[vj[-j]];
    2059:     x[i] = xi;
    2060:   }
    2061:   PetscCall(VecRestoreArrayRead(bb, &b));
    2062:   PetscCall(VecRestoreArray(xx, &x));
    2063:   PetscCall(PetscLogFlops(4.0 * a->nz - 3 * mbs));
    2064:   PetscFunctionReturn(PETSC_SUCCESS);
    2065: }

    2067: PetscErrorCode MatMatSolve_SeqSBAIJ_1_NaturalOrdering(Mat A, Mat B, Mat X)
    2068: {
    2069:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    2070:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *vj, *adiag = a->diag;
    2071:   const MatScalar   *aa = a->a, *v;
    2072:   const PetscScalar *b;
    2073:   PetscScalar       *x, xi;
    2074:   PetscInt           nz, i, j, neq, ldb, ldx;
    2075:   PetscBool          isdense;

    2077:   PetscFunctionBegin;
    2078:   if (!mbs) PetscFunctionReturn(PETSC_SUCCESS);
    2079:   PetscCall(PetscObjectTypeCompare((PetscObject)B, MATSEQDENSE, &isdense));
    2080:   PetscCheck(isdense, PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, "B matrix must be a SeqDense matrix");
    2081:   if (X != B) {
    2082:     PetscCall(PetscObjectTypeCompare((PetscObject)X, MATSEQDENSE, &isdense));
    2083:     PetscCheck(isdense, PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, "X matrix must be a SeqDense matrix");
    2084:   }
    2085:   PetscCall(MatDenseGetArrayRead(B, &b));
    2086:   PetscCall(MatDenseGetLDA(B, &ldb));
    2087:   PetscCall(MatDenseGetArray(X, &x));
    2088:   PetscCall(MatDenseGetLDA(X, &ldx));
    2089:   for (neq = 0; neq < B->cmap->n; neq++) {
    2090:     /* solve U^T*D*y = b by forward substitution */
    2091:     PetscCall(PetscArraycpy(x, b, mbs));
    2092:     for (i = 0; i < mbs; i++) {
    2093:       v  = aa + ai[i];
    2094:       vj = aj + ai[i];
    2095:       xi = x[i];
    2096:       nz = ai[i + 1] - ai[i] - 1; /* exclude diag[i] */
    2097:       for (j = 0; j < nz; j++) x[vj[j]] += v[j] * xi;
    2098:       x[i] = xi * v[nz]; /* v[nz] = aa[diag[i]] = 1/D(i) */
    2099:     }
    2100:     /* solve U*x = y by backward substitution */
    2101:     for (i = mbs - 2; i >= 0; i--) {
    2102:       xi = x[i];
    2103:       v  = aa + adiag[i] - 1; /* end of row i, excluding diag */
    2104:       vj = aj + adiag[i] - 1;
    2105:       nz = ai[i + 1] - ai[i] - 1;
    2106:       for (j = 0; j < nz; j++) xi += v[-j] * x[vj[-j]];
    2107:       x[i] = xi;
    2108:     }
    2109:     b += ldb;
    2110:     x += ldx;
    2111:   }
    2112:   PetscCall(MatDenseRestoreArrayRead(B, &b));
    2113:   PetscCall(MatDenseRestoreArray(X, &x));
    2114:   PetscCall(PetscLogFlops(B->cmap->n * (4.0 * a->nz - 3 * mbs)));
    2115:   PetscFunctionReturn(PETSC_SUCCESS);
    2116: }

    2118: PetscErrorCode MatSolve_SeqSBAIJ_1_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    2119: {
    2120:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    2121:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *vj;
    2122:   const MatScalar   *aa = a->a, *v;
    2123:   PetscScalar       *x, xk;
    2124:   const PetscScalar *b;
    2125:   PetscInt           nz, k;

    2127:   PetscFunctionBegin;
    2128:   PetscCall(VecGetArrayRead(bb, &b));
    2129:   PetscCall(VecGetArray(xx, &x));

    2131:   /* solve U^T*D*y = b by forward substitution */
    2132:   PetscCall(PetscArraycpy(x, b, mbs));
    2133:   for (k = 0; k < mbs; k++) {
    2134:     v  = aa + ai[k] + 1;
    2135:     vj = aj + ai[k] + 1;
    2136:     xk = x[k];
    2137:     nz = ai[k + 1] - ai[k] - 1; /* exclude diag[k] */
    2138:     while (nz--) x[*vj++] += (*v++) * xk;
    2139:     x[k] = xk * aa[ai[k]]; /* note: aa[diag[k]] = 1/D(k) */
    2140:   }

    2142:   /* solve U*x = y by back substitution */
    2143:   for (k = mbs - 2; k >= 0; k--) {
    2144:     v  = aa + ai[k] + 1;
    2145:     vj = aj + ai[k] + 1;
    2146:     xk = x[k];
    2147:     nz = ai[k + 1] - ai[k] - 1;
    2148:     while (nz--) xk += (*v++) * x[*vj++];
    2149:     x[k] = xk;
    2150:   }

    2152:   PetscCall(VecRestoreArrayRead(bb, &b));
    2153:   PetscCall(VecRestoreArray(xx, &x));
    2154:   PetscCall(PetscLogFlops(4.0 * a->nz - 3 * mbs));
    2155:   PetscFunctionReturn(PETSC_SUCCESS);
    2156: }

    2158: PetscErrorCode MatForwardSolve_SeqSBAIJ_1_NaturalOrdering(Mat A, Vec bb, Vec xx)
    2159: {
    2160:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    2161:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *adiag = a->diag, *vj;
    2162:   const MatScalar   *aa = a->a, *v;
    2163:   PetscReal          diagk;
    2164:   PetscScalar       *x;
    2165:   const PetscScalar *b;
    2166:   PetscInt           nz, k;

    2168:   PetscFunctionBegin;
    2169:   /* solve U^T*D^(1/2)*x = b by forward substitution */
    2170:   PetscCall(VecGetArrayRead(bb, &b));
    2171:   PetscCall(VecGetArray(xx, &x));
    2172:   PetscCall(PetscArraycpy(x, b, mbs));
    2173:   for (k = 0; k < mbs; k++) {
    2174:     v  = aa + ai[k];
    2175:     vj = aj + ai[k];
    2176:     nz = ai[k + 1] - ai[k] - 1; /* exclude diag[k] */
    2177:     while (nz--) x[*vj++] += (*v++) * x[k];
    2178:     diagk = PetscRealPart(aa[adiag[k]]); /* note: aa[adiag[k]] = 1/D(k) */
    2179:     PetscCheck(!PetscImaginaryPart(aa[adiag[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal (%g,%g) must be real and nonnegative", (double)PetscRealPart(aa[adiag[k]]), (double)PetscImaginaryPart(aa[adiag[k]]));
    2180:     x[k] *= PetscSqrtReal(diagk);
    2181:   }
    2182:   PetscCall(VecRestoreArrayRead(bb, &b));
    2183:   PetscCall(VecRestoreArray(xx, &x));
    2184:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    2185:   PetscFunctionReturn(PETSC_SUCCESS);
    2186: }

    2188: PetscErrorCode MatForwardSolve_SeqSBAIJ_1_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    2189: {
    2190:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    2191:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *vj;
    2192:   const MatScalar   *aa = a->a, *v;
    2193:   PetscReal          diagk;
    2194:   PetscScalar       *x;
    2195:   const PetscScalar *b;
    2196:   PetscInt           nz, k;

    2198:   PetscFunctionBegin;
    2199:   /* solve U^T*D^(1/2)*x = b by forward substitution */
    2200:   PetscCall(VecGetArrayRead(bb, &b));
    2201:   PetscCall(VecGetArray(xx, &x));
    2202:   PetscCall(PetscArraycpy(x, b, mbs));
    2203:   for (k = 0; k < mbs; k++) {
    2204:     v  = aa + ai[k] + 1;
    2205:     vj = aj + ai[k] + 1;
    2206:     nz = ai[k + 1] - ai[k] - 1; /* exclude diag[k] */
    2207:     while (nz--) x[*vj++] += (*v++) * x[k];
    2208:     diagk = PetscRealPart(aa[ai[k]]); /* note: aa[diag[k]] = 1/D(k) */
    2209:     PetscCheck(!PetscImaginaryPart(aa[ai[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal (%g,%g) must be real and nonnegative", (double)PetscRealPart(aa[ai[k]]), (double)PetscImaginaryPart(aa[ai[k]]));
    2210:     x[k] *= PetscSqrtReal(diagk);
    2211:   }
    2212:   PetscCall(VecRestoreArrayRead(bb, &b));
    2213:   PetscCall(VecRestoreArray(xx, &x));
    2214:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    2215:   PetscFunctionReturn(PETSC_SUCCESS);
    2216: }

    2218: PetscErrorCode MatBackwardSolve_SeqSBAIJ_1_NaturalOrdering(Mat A, Vec bb, Vec xx)
    2219: {
    2220:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    2221:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *adiag = a->diag, *vj;
    2222:   const MatScalar   *aa = a->a, *v;
    2223:   PetscReal          diagk;
    2224:   PetscScalar       *x;
    2225:   const PetscScalar *b;
    2226:   PetscInt           nz, k;

    2228:   PetscFunctionBegin;
    2229:   /* solve D^(1/2)*U*x = b by back substitution */
    2230:   PetscCall(VecGetArrayRead(bb, &b));
    2231:   PetscCall(VecGetArray(xx, &x));

    2233:   for (k = mbs - 1; k >= 0; k--) {
    2234:     v     = aa + ai[k];
    2235:     vj    = aj + ai[k];
    2236:     diagk = PetscRealPart(aa[adiag[k]]); /* note: aa[diag[k]] = 1/D(k) */
    2237:     PetscCheck(!PetscImaginaryPart(aa[adiag[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal must be real and nonnegative");
    2238:     x[k] = PetscSqrtReal(diagk) * b[k];
    2239:     nz   = ai[k + 1] - ai[k] - 1;
    2240:     while (nz--) x[k] += (*v++) * x[*vj++];
    2241:   }
    2242:   PetscCall(VecRestoreArrayRead(bb, &b));
    2243:   PetscCall(VecRestoreArray(xx, &x));
    2244:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    2245:   PetscFunctionReturn(PETSC_SUCCESS);
    2246: }

    2248: PetscErrorCode MatBackwardSolve_SeqSBAIJ_1_NaturalOrdering_inplace(Mat A, Vec bb, Vec xx)
    2249: {
    2250:   Mat_SeqSBAIJ      *a   = (Mat_SeqSBAIJ *)A->data;
    2251:   const PetscInt     mbs = a->mbs, *ai = a->i, *aj = a->j, *vj;
    2252:   const MatScalar   *aa = a->a, *v;
    2253:   PetscReal          diagk;
    2254:   PetscScalar       *x;
    2255:   const PetscScalar *b;
    2256:   PetscInt           nz, k;

    2258:   PetscFunctionBegin;
    2259:   /* solve D^(1/2)*U*x = b by back substitution */
    2260:   PetscCall(VecGetArrayRead(bb, &b));
    2261:   PetscCall(VecGetArray(xx, &x));

    2263:   for (k = mbs - 1; k >= 0; k--) {
    2264:     v     = aa + ai[k] + 1;
    2265:     vj    = aj + ai[k] + 1;
    2266:     diagk = PetscRealPart(aa[ai[k]]); /* note: aa[diag[k]] = 1/D(k) */
    2267:     PetscCheck(!PetscImaginaryPart(aa[ai[k]]) && diagk >= 0, PETSC_COMM_SELF, PETSC_ERR_SUP, "Diagonal must be real and nonnegative");
    2268:     x[k] = PetscSqrtReal(diagk) * b[k];
    2269:     nz   = ai[k + 1] - ai[k] - 1;
    2270:     while (nz--) x[k] += (*v++) * x[*vj++];
    2271:   }
    2272:   PetscCall(VecRestoreArrayRead(bb, &b));
    2273:   PetscCall(VecRestoreArray(xx, &x));
    2274:   PetscCall(PetscLogFlops(2.0 * a->nz - mbs));
    2275:   PetscFunctionReturn(PETSC_SUCCESS);
    2276: }

    2278: /* Use Modified Sparse Row storage for u and ju, see Saad pp.85 */
    2279: static PetscErrorCode MatICCFactorSymbolic_SeqSBAIJ_MSR(Mat B, Mat A, IS perm, const MatFactorInfo *info)
    2280: {
    2281:   Mat_SeqSBAIJ   *a = (Mat_SeqSBAIJ *)A->data, *b;
    2282:   const PetscInt *rip, mbs    = a->mbs, *ai, *aj;
    2283:   PetscInt       *jutmp, bs   = A->rmap->bs, i;
    2284:   PetscInt        m, reallocs = 0, *levtmp;
    2285:   PetscInt       *prowl, *q, jmin, jmax, juidx, nzk, qm, *iu, *ju, k, j, vj, umax, maxadd;
    2286:   PetscInt        incrlev, *lev, shift, prow, nz;
    2287:   PetscReal       f = info->fill, levels = info->levels;
    2288:   PetscBool       perm_identity;

    2290:   PetscFunctionBegin;
    2291:   /* check whether perm is the identity mapping */
    2292:   PetscCall(ISIdentity(perm, &perm_identity));

    2294:   PetscCheck(perm_identity, PETSC_COMM_SELF, PETSC_ERR_SUP, "Matrix reordering is not supported for sbaij matrix. Use aij format");
    2295:   a->permute = PETSC_FALSE;
    2296:   ai         = a->i;
    2297:   aj         = a->j;

    2299:   /* initialization */
    2300:   PetscCall(ISGetIndices(perm, &rip));
    2301:   umax = (PetscInt)(f * ai[mbs] + 1);
    2302:   PetscCall(PetscMalloc1(umax, &lev));
    2303:   umax += mbs + 1;
    2304:   shift = mbs + 1;
    2305:   PetscCall(PetscMalloc1(mbs + 1, &iu));
    2306:   PetscCall(PetscMalloc1(umax, &ju));
    2307:   iu[0] = mbs + 1;
    2308:   juidx = mbs + 1;
    2309:   /* prowl: linked list for pivot row */
    2310:   PetscCall(PetscMalloc3(mbs, &prowl, mbs, &q, mbs, &levtmp));
    2311:   /* q: linked list for col index */

    2313:   for (i = 0; i < mbs; i++) {
    2314:     prowl[i] = mbs;
    2315:     q[i]     = 0;
    2316:   }

    2318:   /* for each row k */
    2319:   for (k = 0; k < mbs; k++) {
    2320:     nzk  = 0;
    2321:     q[k] = mbs;
    2322:     /* copy current row into linked list */
    2323:     nz = ai[rip[k] + 1] - ai[rip[k]];
    2324:     j  = ai[rip[k]];
    2325:     while (nz--) {
    2326:       vj = rip[aj[j++]];
    2327:       if (vj > k) {
    2328:         qm = k;
    2329:         do {
    2330:           m  = qm;
    2331:           qm = q[m];
    2332:         } while (qm < vj);
    2333:         PetscCheck(qm != vj, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Duplicate entry in A");
    2334:         nzk++;
    2335:         q[m]       = vj;
    2336:         q[vj]      = qm;
    2337:         levtmp[vj] = 0; /* initialize lev for nonzero element */
    2338:       }
    2339:     }

    2341:     /* modify nonzero structure of k-th row by computing fill-in
    2342:        for each row prow to be merged in */
    2343:     prow = k;
    2344:     prow = prowl[prow]; /* next pivot row (== 0 for symbolic factorization) */

    2346:     while (prow < k) {
    2347:       /* merge row prow into k-th row */
    2348:       jmin = iu[prow] + 1;
    2349:       jmax = iu[prow + 1];
    2350:       qm   = k;
    2351:       for (j = jmin; j < jmax; j++) {
    2352:         incrlev = lev[j - shift] + 1;
    2353:         if (incrlev > levels) continue;
    2354:         vj = ju[j];
    2355:         do {
    2356:           m  = qm;
    2357:           qm = q[m];
    2358:         } while (qm < vj);
    2359:         if (qm != vj) { /* a fill */
    2360:           nzk++;
    2361:           q[m]       = vj;
    2362:           q[vj]      = qm;
    2363:           qm         = vj;
    2364:           levtmp[vj] = incrlev;
    2365:         } else if (levtmp[vj] > incrlev) levtmp[vj] = incrlev;
    2366:       }
    2367:       prow = prowl[prow]; /* next pivot row */
    2368:     }

    2370:     /* add k to row list for first nonzero element in k-th row */
    2371:     if (nzk > 1) {
    2372:       i        = q[k]; /* col value of first nonzero element in k_th row of U */
    2373:       prowl[k] = prowl[i];
    2374:       prowl[i] = k;
    2375:     }
    2376:     iu[k + 1] = iu[k] + nzk;

    2378:     /* allocate more space to ju and lev if needed */
    2379:     if (iu[k + 1] > umax) {
    2380:       /* estimate how much additional space we will need */
    2381:       /* use the strategy suggested by David Hysom <hysom@perch-t.icase.edu> */
    2382:       /* just double the memory each time */
    2383:       maxadd = umax;
    2384:       if (maxadd < nzk) maxadd = (mbs - k) * (nzk + 1) / 2;
    2385:       umax += maxadd;

    2387:       /* allocate a longer ju */
    2388:       PetscCall(PetscMalloc1(umax, &jutmp));
    2389:       PetscCall(PetscArraycpy(jutmp, ju, iu[k]));
    2390:       PetscCall(PetscFree(ju));
    2391:       ju = jutmp;

    2393:       PetscCall(PetscMalloc1(umax, &jutmp));
    2394:       PetscCall(PetscArraycpy(jutmp, lev, iu[k] - shift));
    2395:       PetscCall(PetscFree(lev));
    2396:       lev = jutmp;
    2397:       reallocs += 2; /* count how many times we realloc */
    2398:     }

    2400:     /* save nonzero structure of k-th row in ju */
    2401:     i = k;
    2402:     while (nzk--) {
    2403:       i                  = q[i];
    2404:       ju[juidx]          = i;
    2405:       lev[juidx - shift] = levtmp[i];
    2406:       juidx++;
    2407:     }
    2408:   }

    2410: #if defined(PETSC_USE_INFO)
    2411:   if (ai[mbs] != 0) {
    2412:     PetscReal af = ((PetscReal)iu[mbs]) / ((PetscReal)ai[mbs]);
    2413:     PetscCall(PetscInfo(A, "Reallocs %" PetscInt_FMT " Fill ratio:given %g needed %g\n", reallocs, (double)f, (double)af));
    2414:     PetscCall(PetscInfo(A, "Run with -pc_factor_fill %g or use \n", (double)af));
    2415:     PetscCall(PetscInfo(A, "PCFactorSetFill(pc,%g);\n", (double)af));
    2416:     PetscCall(PetscInfo(A, "for best performance.\n"));
    2417:   } else {
    2418:     PetscCall(PetscInfo(A, "Empty matrix\n"));
    2419:   }
    2420: #endif

    2422:   PetscCall(ISRestoreIndices(perm, &rip));
    2423:   PetscCall(PetscFree3(prowl, q, levtmp));
    2424:   PetscCall(PetscFree(lev));

    2426:   /* put together the new matrix */
    2427:   PetscCall(MatSeqSBAIJSetPreallocation(B, bs, 0, NULL));

    2429:   b = (Mat_SeqSBAIJ *)B->data;
    2430:   PetscCall(PetscFree2(b->imax, b->ilen));

    2432:   /* the next line frees the default space generated by the Create() */
    2433:   PetscCall(MatSeqXAIJFreeAIJ(B, &b->a, &b->j, &b->i));
    2434:   PetscCall(PetscShmgetAllocateArray((iu[mbs] + 1) * a->bs2, sizeof(PetscScalar), (void **)&b->a));
    2435:   b->free_a  = PETSC_TRUE;
    2436:   b->free_ij = PETSC_TRUE;
    2437:   b->j       = ju;
    2438:   b->i       = iu;
    2439:   b->diag    = NULL;
    2440:   b->ilen    = NULL;
    2441:   b->imax    = NULL;

    2443:   PetscCall(ISDestroy(&b->row));
    2444:   PetscCall(ISDestroy(&b->icol));
    2445:   b->row  = perm;
    2446:   b->icol = perm;
    2447:   PetscCall(PetscObjectReference((PetscObject)perm));
    2448:   PetscCall(PetscObjectReference((PetscObject)perm));
    2449:   PetscCall(PetscMalloc1(bs * mbs + bs, &b->solve_work));
    2450:   /* In b structure:  Free imax, ilen, old a, old j.
    2451:      Allocate idnew, solve_work, new a, new j */
    2452:   b->maxnz = b->nz = iu[mbs];

    2454:   B->info.factor_mallocs   = reallocs;
    2455:   B->info.fill_ratio_given = f;
    2456:   if (ai[mbs] != 0) {
    2457:     B->info.fill_ratio_needed = ((PetscReal)iu[mbs]) / ((PetscReal)ai[mbs]);
    2458:   } else {
    2459:     B->info.fill_ratio_needed = 0.0;
    2460:   }
    2461:   PetscCall(MatSeqSBAIJSetNumericFactorization_inplace(B, perm_identity));
    2462:   PetscFunctionReturn(PETSC_SUCCESS);
    2463: }

    2465: /*
    2466:   See MatICCFactorSymbolic_SeqAIJ() for description of its data structure
    2467: */
    2468: #include <petscbt.h>
    2469: #include <../src/mat/utils/freespace.h>
    2470: PetscErrorCode MatICCFactorSymbolic_SeqSBAIJ(Mat fact, Mat A, IS perm, const MatFactorInfo *info)
    2471: {
    2472:   Mat_SeqSBAIJ      *a = (Mat_SeqSBAIJ *)A->data, *b;
    2473:   PetscBool          perm_identity, free_ij = PETSC_TRUE, missing;
    2474:   PetscInt           bs = A->rmap->bs, am = a->mbs, d, *ai = a->i, *aj = a->j;
    2475:   const PetscInt    *rip;
    2476:   PetscInt           reallocs = 0, i, *ui, *udiag, *cols;
    2477:   PetscInt           jmin, jmax, nzk, k, j, *jl, prow, *il, nextprow;
    2478:   PetscInt           nlnk, *lnk, *lnk_lvl = NULL, ncols, *uj, **uj_ptr, **uj_lvl_ptr;
    2479:   PetscReal          fill = info->fill, levels = info->levels;
    2480:   PetscFreeSpaceList free_space = NULL, current_space = NULL;
    2481:   PetscFreeSpaceList free_space_lvl = NULL, current_space_lvl = NULL;
    2482:   PetscBT            lnkbt;

    2484:   PetscFunctionBegin;
    2485:   PetscCheck(A->rmap->n == A->cmap->n, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Must be square matrix, rows %" PetscInt_FMT " columns %" PetscInt_FMT, A->rmap->n, A->cmap->n);
    2486:   PetscCall(MatMissingDiagonal(A, &missing, &d));
    2487:   PetscCheck(!missing, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONGSTATE, "Matrix is missing diagonal entry %" PetscInt_FMT, d);
    2488:   if (bs > 1) {
    2489:     PetscCall(MatICCFactorSymbolic_SeqSBAIJ_inplace(fact, A, perm, info));
    2490:     PetscFunctionReturn(PETSC_SUCCESS);
    2491:   }

    2493:   /* check whether perm is the identity mapping */
    2494:   PetscCall(ISIdentity(perm, &perm_identity));
    2495:   PetscCheck(perm_identity, PETSC_COMM_SELF, PETSC_ERR_SUP, "Matrix reordering is not supported for sbaij matrix. Use aij format");
    2496:   a->permute = PETSC_FALSE;

    2498:   PetscCall(PetscMalloc1(am + 1, &ui));
    2499:   PetscCall(PetscMalloc1(am + 1, &udiag));
    2500:   ui[0] = 0;

    2502:   /* ICC(0) without matrix ordering: simply rearrange column indices */
    2503:   if (!levels) {
    2504:     /* reuse the column pointers and row offsets for memory savings */
    2505:     for (i = 0; i < am; i++) {
    2506:       ncols     = ai[i + 1] - ai[i];
    2507:       ui[i + 1] = ui[i] + ncols;
    2508:       udiag[i]  = ui[i + 1] - 1; /* points to the last entry of U(i,:) */
    2509:     }
    2510:     PetscCall(PetscMalloc1(ui[am], &uj));
    2511:     cols = uj;
    2512:     for (i = 0; i < am; i++) {
    2513:       aj    = a->j + ai[i] + 1; /* 1st entry of U(i,:) without diagonal */
    2514:       ncols = ai[i + 1] - ai[i] - 1;
    2515:       for (j = 0; j < ncols; j++) *cols++ = aj[j];
    2516:       *cols++ = i; /* diagonal is located as the last entry of U(i,:) */
    2517:     }
    2518:   } else { /* case: levels>0 */
    2519:     PetscCall(ISGetIndices(perm, &rip));

    2521:     /* initialization */
    2522:     /* jl: linked list for storing indices of the pivot rows
    2523:        il: il[i] points to the 1st nonzero entry of U(i,k:am-1) */
    2524:     PetscCall(PetscMalloc4(am, &uj_ptr, am, &uj_lvl_ptr, am, &il, am, &jl));
    2525:     for (i = 0; i < am; i++) {
    2526:       jl[i] = am;
    2527:       il[i] = 0;
    2528:     }

    2530:     /* create and initialize a linked list for storing column indices of the active row k */
    2531:     nlnk = am + 1;
    2532:     PetscCall(PetscIncompleteLLCreate(am, am, nlnk, lnk, lnk_lvl, lnkbt));

    2534:     /* initial FreeSpace size is fill*(ai[am]+1) */
    2535:     PetscCall(PetscFreeSpaceGet(PetscRealIntMultTruncate(fill, ai[am] + 1), &free_space));

    2537:     current_space = free_space;

    2539:     PetscCall(PetscFreeSpaceGet(PetscRealIntMultTruncate(fill, ai[am] + 1), &free_space_lvl));

    2541:     current_space_lvl = free_space_lvl;

    2543:     for (k = 0; k < am; k++) { /* for each active row k */
    2544:       /* initialize lnk by the column indices of row k */
    2545:       nzk   = 0;
    2546:       ncols = ai[k + 1] - ai[k];
    2547:       PetscCheck(ncols, PETSC_COMM_SELF, PETSC_ERR_MAT_CH_ZRPVT, "Empty row %" PetscInt_FMT " in matrix ", k);
    2548:       cols = aj + ai[k];
    2549:       PetscCall(PetscIncompleteLLInit(ncols, cols, am, rip, &nlnk, lnk, lnk_lvl, lnkbt));
    2550:       nzk += nlnk;

    2552:       /* update lnk by computing fill-in for each pivot row to be merged in */
    2553:       prow = jl[k]; /* 1st pivot row */

    2555:       while (prow < k) {
    2556:         nextprow = jl[prow];

    2558:         /* merge prow into k-th row */
    2559:         jmin  = il[prow] + 1; /* index of the 2nd nzero entry in U(prow,k:am-1) */
    2560:         jmax  = ui[prow + 1];
    2561:         ncols = jmax - jmin;
    2562:         i     = jmin - ui[prow];

    2564:         cols = uj_ptr[prow] + i;     /* points to the 2nd nzero entry in U(prow,k:am-1) */
    2565:         uj   = uj_lvl_ptr[prow] + i; /* levels of cols */
    2566:         j    = *(uj - 1);
    2567:         PetscCall(PetscICCLLAddSorted(ncols, cols, levels, uj, am, &nlnk, lnk, lnk_lvl, lnkbt, j));
    2568:         nzk += nlnk;

    2570:         /* update il and jl for prow */
    2571:         if (jmin < jmax) {
    2572:           il[prow] = jmin;

    2574:           j        = *cols;
    2575:           jl[prow] = jl[j];
    2576:           jl[j]    = prow;
    2577:         }
    2578:         prow = nextprow;
    2579:       }

    2581:       /* if free space is not available, make more free space */
    2582:       if (current_space->local_remaining < nzk) {
    2583:         i = am - k + 1;                                    /* num of unfactored rows */
    2584:         i = PetscIntMultTruncate(i, PetscMin(nzk, i - 1)); /* i*nzk, i*(i-1): estimated and max additional space needed */
    2585:         PetscCall(PetscFreeSpaceGet(i, &current_space));
    2586:         PetscCall(PetscFreeSpaceGet(i, &current_space_lvl));
    2587:         reallocs++;
    2588:       }

    2590:       /* copy data into free_space and free_space_lvl, then initialize lnk */
    2591:       PetscCheck(nzk != 0, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Empty row %" PetscInt_FMT " in ICC matrix factor", k);
    2592:       PetscCall(PetscIncompleteLLClean(am, am, nzk, lnk, lnk_lvl, current_space->array, current_space_lvl->array, lnkbt));

    2594:       /* add the k-th row into il and jl */
    2595:       if (nzk > 1) {
    2596:         i     = current_space->array[1]; /* col value of the first nonzero element in U(k, k+1:am-1) */
    2597:         jl[k] = jl[i];
    2598:         jl[i] = k;
    2599:         il[k] = ui[k] + 1;
    2600:       }
    2601:       uj_ptr[k]     = current_space->array;
    2602:       uj_lvl_ptr[k] = current_space_lvl->array;

    2604:       current_space->array += nzk;
    2605:       current_space->local_used += nzk;
    2606:       current_space->local_remaining -= nzk;
    2607:       current_space_lvl->array += nzk;
    2608:       current_space_lvl->local_used += nzk;
    2609:       current_space_lvl->local_remaining -= nzk;

    2611:       ui[k + 1] = ui[k] + nzk;
    2612:     }

    2614:     PetscCall(ISRestoreIndices(perm, &rip));
    2615:     PetscCall(PetscFree4(uj_ptr, uj_lvl_ptr, il, jl));

    2617:     /* destroy list of free space and other temporary array(s) */
    2618:     PetscCall(PetscMalloc1(ui[am], &uj));
    2619:     PetscCall(PetscFreeSpaceContiguous_Cholesky(&free_space, uj, am, ui, udiag)); /* store matrix factor  */
    2620:     PetscCall(PetscIncompleteLLDestroy(lnk, lnkbt));
    2621:     PetscCall(PetscFreeSpaceDestroy(free_space_lvl));

    2623:   } /* end of case: levels>0 || (levels=0 && !perm_identity) */

    2625:   /* put together the new matrix in MATSEQSBAIJ format */
    2626:   PetscCall(MatSeqSBAIJSetPreallocation(fact, bs, MAT_SKIP_ALLOCATION, NULL));

    2628:   b = (Mat_SeqSBAIJ *)fact->data;
    2629:   PetscCall(PetscFree2(b->imax, b->ilen));
    2630:   PetscCall(PetscShmgetAllocateArray(ui[am], sizeof(PetscScalar), (void **)&b->a));
    2631:   b->free_a    = PETSC_TRUE;
    2632:   b->free_ij   = free_ij;
    2633:   b->j         = uj;
    2634:   b->i         = ui;
    2635:   b->diag      = udiag;
    2636:   b->free_diag = PETSC_TRUE;
    2637:   b->ilen      = NULL;
    2638:   b->imax      = NULL;
    2639:   b->row       = perm;
    2640:   b->col       = perm;

    2642:   PetscCall(PetscObjectReference((PetscObject)perm));
    2643:   PetscCall(PetscObjectReference((PetscObject)perm));

    2645:   b->pivotinblocks = PETSC_FALSE; /* need to get from MatFactorInfo */

    2647:   PetscCall(PetscMalloc1(am + 1, &b->solve_work));

    2649:   b->maxnz = b->nz = ui[am];

    2651:   fact->info.factor_mallocs   = reallocs;
    2652:   fact->info.fill_ratio_given = fill;
    2653:   if (ai[am] != 0) {
    2654:     fact->info.fill_ratio_needed = ((PetscReal)ui[am]) / ai[am];
    2655:   } else {
    2656:     fact->info.fill_ratio_needed = 0.0;
    2657:   }
    2658: #if defined(PETSC_USE_INFO)
    2659:   if (ai[am] != 0) {
    2660:     PetscReal af = fact->info.fill_ratio_needed;
    2661:     PetscCall(PetscInfo(A, "Reallocs %" PetscInt_FMT " Fill ratio:given %g needed %g\n", reallocs, (double)fill, (double)af));
    2662:     PetscCall(PetscInfo(A, "Run with -pc_factor_fill %g or use \n", (double)af));
    2663:     PetscCall(PetscInfo(A, "PCFactorSetFill(pc,%g) for best performance.\n", (double)af));
    2664:   } else {
    2665:     PetscCall(PetscInfo(A, "Empty matrix\n"));
    2666:   }
    2667: #endif
    2668:   fact->ops->choleskyfactornumeric = MatCholeskyFactorNumeric_SeqSBAIJ_1_NaturalOrdering;
    2669:   PetscFunctionReturn(PETSC_SUCCESS);
    2670: }

    2672: PetscErrorCode MatICCFactorSymbolic_SeqSBAIJ_inplace(Mat fact, Mat A, IS perm, const MatFactorInfo *info)
    2673: {
    2674:   Mat_SeqSBAIJ      *a = (Mat_SeqSBAIJ *)A->data;
    2675:   Mat_SeqSBAIJ      *b;
    2676:   PetscBool          perm_identity, free_ij = PETSC_TRUE;
    2677:   PetscInt           bs = A->rmap->bs, am = a->mbs;
    2678:   const PetscInt    *cols, *rip, *ai = a->i, *aj = a->j;
    2679:   PetscInt           reallocs = 0, i, *ui;
    2680:   PetscInt           jmin, jmax, nzk, k, j, *jl, prow, *il, nextprow;
    2681:   PetscInt           nlnk, *lnk, *lnk_lvl = NULL, ncols, *cols_lvl, *uj, **uj_ptr, **uj_lvl_ptr;
    2682:   PetscReal          fill = info->fill, levels = info->levels, ratio_needed;
    2683:   PetscFreeSpaceList free_space = NULL, current_space = NULL;
    2684:   PetscFreeSpaceList free_space_lvl = NULL, current_space_lvl = NULL;
    2685:   PetscBT            lnkbt;

    2687:   PetscFunctionBegin;
    2688:   /*
    2689:    This code originally uses Modified Sparse Row (MSR) storage
    2690:    (see page 85, "Iterative Methods ..." by Saad) for the output matrix B - bad choice!
    2691:    Then it is rewritten so the factor B takes seqsbaij format. However the associated
    2692:    MatCholeskyFactorNumeric_() have not been modified for the cases of bs>1,
    2693:    thus the original code in MSR format is still used for these cases.
    2694:    The code below should replace MatICCFactorSymbolic_SeqSBAIJ_MSR() whenever
    2695:    MatCholeskyFactorNumeric_() is modified for using sbaij symbolic factor.
    2696:   */
    2697:   if (bs > 1) {
    2698:     PetscCall(MatICCFactorSymbolic_SeqSBAIJ_MSR(fact, A, perm, info));
    2699:     PetscFunctionReturn(PETSC_SUCCESS);
    2700:   }

    2702:   /* check whether perm is the identity mapping */
    2703:   PetscCall(ISIdentity(perm, &perm_identity));
    2704:   PetscCheck(perm_identity, PETSC_COMM_SELF, PETSC_ERR_SUP, "Matrix reordering is not supported for sbaij matrix. Use aij format");
    2705:   a->permute = PETSC_FALSE;

    2707:   /* special case that simply copies fill pattern */
    2708:   if (!levels) {
    2709:     /* reuse the column pointers and row offsets for memory savings */
    2710:     ui           = a->i;
    2711:     uj           = a->j;
    2712:     free_ij      = PETSC_FALSE;
    2713:     ratio_needed = 1.0;
    2714:   } else { /* case: levels>0 */
    2715:     PetscCall(ISGetIndices(perm, &rip));

    2717:     /* initialization */
    2718:     PetscCall(PetscMalloc1(am + 1, &ui));
    2719:     ui[0] = 0;

    2721:     /* jl: linked list for storing indices of the pivot rows
    2722:        il: il[i] points to the 1st nonzero entry of U(i,k:am-1) */
    2723:     PetscCall(PetscMalloc4(am, &uj_ptr, am, &uj_lvl_ptr, am, &il, am, &jl));
    2724:     for (i = 0; i < am; i++) {
    2725:       jl[i] = am;
    2726:       il[i] = 0;
    2727:     }

    2729:     /* create and initialize a linked list for storing column indices of the active row k */
    2730:     nlnk = am + 1;
    2731:     PetscCall(PetscIncompleteLLCreate(am, am, nlnk, lnk, lnk_lvl, lnkbt));

    2733:     /* initial FreeSpace size is fill*(ai[am]+1) */
    2734:     PetscCall(PetscFreeSpaceGet(PetscRealIntMultTruncate(fill, ai[am] + 1), &free_space));

    2736:     current_space = free_space;

    2738:     PetscCall(PetscFreeSpaceGet(PetscRealIntMultTruncate(fill, ai[am] + 1), &free_space_lvl));

    2740:     current_space_lvl = free_space_lvl;

    2742:     for (k = 0; k < am; k++) { /* for each active row k */
    2743:       /* initialize lnk by the column indices of row rip[k] */
    2744:       nzk   = 0;
    2745:       ncols = ai[rip[k] + 1] - ai[rip[k]];
    2746:       cols  = aj + ai[rip[k]];
    2747:       PetscCall(PetscIncompleteLLInit(ncols, cols, am, rip, &nlnk, lnk, lnk_lvl, lnkbt));
    2748:       nzk += nlnk;

    2750:       /* update lnk by computing fill-in for each pivot row to be merged in */
    2751:       prow = jl[k]; /* 1st pivot row */

    2753:       while (prow < k) {
    2754:         nextprow = jl[prow];

    2756:         /* merge prow into k-th row */
    2757:         jmin     = il[prow] + 1; /* index of the 2nd nzero entry in U(prow,k:am-1) */
    2758:         jmax     = ui[prow + 1];
    2759:         ncols    = jmax - jmin;
    2760:         i        = jmin - ui[prow];
    2761:         cols     = uj_ptr[prow] + i; /* points to the 2nd nzero entry in U(prow,k:am-1) */
    2762:         j        = *(uj_lvl_ptr[prow] + i - 1);
    2763:         cols_lvl = uj_lvl_ptr[prow] + i;
    2764:         PetscCall(PetscICCLLAddSorted(ncols, cols, levels, cols_lvl, am, &nlnk, lnk, lnk_lvl, lnkbt, j));
    2765:         nzk += nlnk;

    2767:         /* update il and jl for prow */
    2768:         if (jmin < jmax) {
    2769:           il[prow] = jmin;
    2770:           j        = *cols;
    2771:           jl[prow] = jl[j];
    2772:           jl[j]    = prow;
    2773:         }
    2774:         prow = nextprow;
    2775:       }

    2777:       /* if free space is not available, make more free space */
    2778:       if (current_space->local_remaining < nzk) {
    2779:         i = am - k + 1;                                                             /* num of unfactored rows */
    2780:         i = PetscMin(PetscIntMultTruncate(i, nzk), PetscIntMultTruncate(i, i - 1)); /* i*nzk, i*(i-1): estimated and max additional space needed */
    2781:         PetscCall(PetscFreeSpaceGet(i, &current_space));
    2782:         PetscCall(PetscFreeSpaceGet(i, &current_space_lvl));
    2783:         reallocs++;
    2784:       }

    2786:       /* copy data into free_space and free_space_lvl, then initialize lnk */
    2787:       PetscCall(PetscIncompleteLLClean(am, am, nzk, lnk, lnk_lvl, current_space->array, current_space_lvl->array, lnkbt));

    2789:       /* add the k-th row into il and jl */
    2790:       if (nzk - 1 > 0) {
    2791:         i     = current_space->array[1]; /* col value of the first nonzero element in U(k, k+1:am-1) */
    2792:         jl[k] = jl[i];
    2793:         jl[i] = k;
    2794:         il[k] = ui[k] + 1;
    2795:       }
    2796:       uj_ptr[k]     = current_space->array;
    2797:       uj_lvl_ptr[k] = current_space_lvl->array;

    2799:       current_space->array += nzk;
    2800:       current_space->local_used += nzk;
    2801:       current_space->local_remaining -= nzk;
    2802:       current_space_lvl->array += nzk;
    2803:       current_space_lvl->local_used += nzk;
    2804:       current_space_lvl->local_remaining -= nzk;

    2806:       ui[k + 1] = ui[k] + nzk;
    2807:     }

    2809:     PetscCall(ISRestoreIndices(perm, &rip));
    2810:     PetscCall(PetscFree4(uj_ptr, uj_lvl_ptr, il, jl));

    2812:     /* destroy list of free space and other temporary array(s) */
    2813:     PetscCall(PetscMalloc1(ui[am] + 1, &uj));
    2814:     PetscCall(PetscFreeSpaceContiguous(&free_space, uj));
    2815:     PetscCall(PetscIncompleteLLDestroy(lnk, lnkbt));
    2816:     PetscCall(PetscFreeSpaceDestroy(free_space_lvl));
    2817:     if (ai[am] != 0) {
    2818:       ratio_needed = ((PetscReal)ui[am]) / ((PetscReal)ai[am]);
    2819:     } else {
    2820:       ratio_needed = 0.0;
    2821:     }
    2822:   } /* end of case: levels>0 || (levels=0 && !perm_identity) */

    2824:   /* put together the new matrix in MATSEQSBAIJ format */
    2825:   PetscCall(MatSeqSBAIJSetPreallocation(fact, bs, MAT_SKIP_ALLOCATION, NULL));

    2827:   b = (Mat_SeqSBAIJ *)fact->data;
    2828:   PetscCall(PetscFree2(b->imax, b->ilen));
    2829:   PetscCall(PetscShmgetAllocateArray(ui[am], sizeof(PetscScalar), (void **)&b->a));
    2830:   b->free_a        = PETSC_TRUE;
    2831:   b->free_ij       = free_ij;
    2832:   b->j             = uj;
    2833:   b->i             = ui;
    2834:   b->diag          = NULL;
    2835:   b->ilen          = NULL;
    2836:   b->imax          = NULL;
    2837:   b->row           = perm;
    2838:   b->pivotinblocks = PETSC_FALSE; /* need to get from MatFactorInfo */

    2840:   PetscCall(PetscObjectReference((PetscObject)perm));
    2841:   b->icol = perm;
    2842:   PetscCall(PetscObjectReference((PetscObject)perm));
    2843:   PetscCall(PetscMalloc1(am + 1, &b->solve_work));

    2845:   b->maxnz = b->nz = ui[am];

    2847:   fact->info.factor_mallocs    = reallocs;
    2848:   fact->info.fill_ratio_given  = fill;
    2849:   fact->info.fill_ratio_needed = ratio_needed;
    2850: #if defined(PETSC_USE_INFO)
    2851:   if (ai[am] != 0) {
    2852:     PetscReal af = fact->info.fill_ratio_needed;
    2853:     PetscCall(PetscInfo(A, "Reallocs %" PetscInt_FMT " Fill ratio:given %g needed %g\n", reallocs, (double)fill, (double)af));
    2854:     PetscCall(PetscInfo(A, "Run with -pc_factor_fill %g or use \n", (double)af));
    2855:     PetscCall(PetscInfo(A, "PCFactorSetFill(pc,%g) for best performance.\n", (double)af));
    2856:   } else {
    2857:     PetscCall(PetscInfo(A, "Empty matrix\n"));
    2858:   }
    2859: #endif
    2860:   if (perm_identity) {
    2861:     fact->ops->choleskyfactornumeric = MatCholeskyFactorNumeric_SeqSBAIJ_1_NaturalOrdering_inplace;
    2862:   } else {
    2863:     fact->ops->choleskyfactornumeric = MatCholeskyFactorNumeric_SeqSBAIJ_1_inplace;
    2864:   }
    2865:   PetscFunctionReturn(PETSC_SUCCESS);
    2866: }