scientific article; zbMATH DE number 3967813
[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).
- Efficient parallel linear programming
- Fast and Efficient Parallel Solution of Sparse Linear Systems
- Parallel solution of sparse linear least squares problems on distributed-memory multiprocessors
- Parallel algorithms for the iterative solution of sparse least-squares problems
- Fast and efficient linear programming and linear least-squares computations
- Efficient parallel linear programming
- PCR algorithm for parallel computing minimum-norm (T) least-squares (S) solution of inconsistent linear equations
- Using massively parallel computations for absolutely precise solution of the linear programming problems
- scientific article; zbMATH DE number 6378086 (Why is no real title available?)
- Fast and efficient linear programming and linear least-squares computations
- Efficient Parallel Nonnegative Least Squares on Multicore Architectures
- Efficiency of parallel macropipelined computations in partially blocked linear and 0?1 linear programming problems
- scientific article; zbMATH DE number 4056886 (Why is no real title available?)
- A Parallel Nonlinear Least-Squares Solver: Theoretical Analysis and Numerical Results
- Fast and Efficient Parallel Solution of Sparse Linear Systems
- Efficient high-precision matrix algebra on parallel architectures for nonlinear combinatorial optimization
- Parallel Cholesky-based reduction for the weighted integer least squares problem
- Parallel algorithms for the iterative solution of sparse least-squares problems
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)