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

      0 references
      0 references
      1986
      0 references
      parallel algorithms
      0 references
      least-squares solution
      0 references
      overdetermined linear system
      0 references
      nested dissection
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references