No label defined (Q3734987)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3967813
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3967813 |
Statements
1986
0 references
parallel algorithms
0 references
least-squares solution
0 references
overdetermined linear system
0 references
nested dissection
0 references
0.8810280561447144
0 references
0.8577970266342163
0 references
0.8533570766448975
0 references
0.8337270617485046
0 references
0.8305810689926147
0 references
[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).
0 references