A new efficient solution method for a system of linear equations: Partially Solving Method (PSM) (Q1922228)

The authors present an approach to organizing the direct solution of the \(n\times n\) matrix equation \(Ax=b\). The basic idea can be expressed as a recursion. Assume that \(k\leq n\) unknowns have been expressed in terms of the others as \(I_kx_k=A_{n-k}x_{n-k}+ b_k\). \(I_k\) represents the \(k\times k\) identity matrix, \(x_k\) the \(k\)-vector whose elements are the first \(k\) elements of \(x\), \(A_{n-k}\) is an \((n-k)\times k\) matrix, \(x_{n-k}\) is an \((n-k)\)-vector whose elements are the final \(n-k\) elements of \(x\) and \(b_k\) is a \(k\)-vector. A component of \(x\) can be moved from the right to the left side by augmenting \(I_k\) with a single row and column from part of the matrix \(A_{n-k}\) and solving. When \(k=n\), the entire system is solved. The authors assume that the diagonal entries of \(A\) are non-zero and that the induction step does not give rise to a singular matrix. They provide operation counts and estimates of memory space required for implementation, but the required memory is in addition to that required by \(A\). The operation count is half that required by pure Gaussian elimination for very sparse matrices.