A Block Projection Method for Sparse Matrices

For the solution of systems of linear algebraic equations with sparse matrices the block Cimmino method is employed. Let the system be written as \[ \begin{pmatrix} A^ 1\\A^ 2\\\vdots\\ A^ p\end{pmatrix} x=\begin{pmatrix} b^ 1\\ b^ 2\\ \vdots \\b^ p\end{pmatrix} \] where the \(A^ i\) are matrices and the \(b^ i\) vectors. Let \(P_{R(A^ i)^ T}\) be the projector onto the image of the operator \((A^ i)^ T\) and \((A^ i)^ +\) be the matrix pseudo-inverse to \(A^ i\). The block Cimmino method has the following form: \(x^{(0)}\) is given, and it is assumed that \(k=0\). Before convergence is obtained the following calculations are performed: begin do in parallel for \(i=1(1)p\) \[ \delta^{i^{(K)}}=(A^ i)^ +b^ i- P_{R(A^ i)^ T}x^{(k)}=(A^ i)^ =(b^ i-A^ ix^{(k)}) \] \[ x^{(k+1)}:=x^{(k)}+\omega\sum^ p_{i=1}\delta^{i(k)} \] \[ k:=k+1 \] end. Special consideration is given to a block tridiagonal matrix. In order to accelerate convergence the method of conjugate gradients is employed. The convergence of the iteration strongly depends on the block partitioning of the input matrix. Several possible partitions are shown. Four tests are considered, numerical experiments with them are performed on an eight-processor computer Alliant FX/80. Block tridiagonal matrices are tested. The first system is obtained by an approximation of the Navier-Stokes equations coupled with the chemical kinetic equations by the finite volumes method. The second system is obtained by a similar approximation of the Euler equations of a transonic flow. The third system is the finite-difference approximation of the two- dimensional elliptic equation \(-u_{xx}-u_{yy}+1000e^{xy}(u_ x- u_ y)=g\) where the right-hand side \(g\) is selected so that the equation has the solution \(u=x+y\). The fourth system arises as the seven-point finite-difference approximation of the equation \(u_{xx}+u_{yy}+u_{zz}+100xu_ x-zu_ z+100(x+y+z)\cdot(xyz)^{- 1}u=F\) where the right-hand side is selected so that the equation has the solution \(u=\exp(xyz)\cdot\sin(\pi x)\cdot\sin(\pi y)\cdot\sin(\pi z)\). For these problems the effect of matrix scaling partitioning is studied. Rapid convergence for all tests is obtained.

Recommendations

Cited in

(24)

This page was built for publication: A Block Projection Method for Sparse Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990903)