scientific article; zbMATH DE number 3967813

From MaRDI portal
Publication:3734987





[For the entire collection see Zbl 0587.00021.] A new parallel algorithm is presented for computing a least-squares solution to a sparse overdetermined linear system of linear equations \(Ax=b\), such that the \(m\times m\) matrix A is sparse, and the graph of \(H=\left[ \begin{matrix} I\\ A\end{matrix}\begin{matrix} A^ T\\ 0\end{matrix} \right]\) has an \(s(m+n)\)-separator family (a customary assumption for the users of the important methods of nested dissection). The algorithm uses \(O(\log^ 3(m+n))\) steps and \(\leq s(m+n)^ 3\) processors, extending authors' previous parallel nested dissection algorithm for linear systems. There are several further extensions and applications; in particular, to the linear programming, where the current best sequential arithmetic time of \(O(m^{3.5}L)\) of Karmarkar (L is the input size) is improved to \(O(mL(s(m+n))^ 3\log m \log^ 2s(m+n))\) arithmetic operations (or to \(O(m L\log m\log^ 2s(m+n))\) parallel arithmetic steps, \(s(m+n)^ 3\) processors) in the important practical case where for the input matrix A, the matrix H has \(s(m+n)\)-separator family. The journal version of the paper appeared in Comput. Math. Appl., Part A 12, 1217-1227 (1986).











This page was built for publication:

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