Fast and Efficient Parallel Solution of Sparse Linear Systems

From MaRDI portal





The authors present a numerically stable parallel algorithm for a sparse \(n\times n\) symmetric positive definite linear system \(Ax = b\) that can be solved by a sequential algorithm based on the generalized nested dissection of the associated graph \(G(A)\). The algorithm is effective for systems whose associated graphs have \(s(n)\)-separator families and for which \(s(n)\)-separator trees are readily available. In such a case, the algorithm requires only \(O(\log^ 3n)\) time and \((| E| + M(s(n)))/\log n\) processors for the evaluation of the solution vector \(x = A^{-1}b\) where \(| E|\) is the number of edges in \(G(A)\) and \(M(n)\) is the number of processors sufficient for multiplying two \(n\times n\) rational matrices in time \(O(\log n)\). The algorithm is compared with previous results, and some complexity estimates are given. Some applications are also listed.




Cited in
(41)








This page was built for publication: Fast and Efficient Parallel Solution of Sparse Linear Systems

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