Skip to main content
SpringerLink
Log in

The solution of large-scale least-squares problems on supercomputers

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We discuss methods for solving medium to large-scale sparse least-squares problems on supercomputers, illustrating our remarks by experiments on the CRAY-2 supercomputer at Harwell. The method we are primarily concerned with is an augmented system approach which has the merit of both robustness and accuracy, in addition to a kernel operation that is just the solution of a symmetric indefinite system. We consider extensions to handle weighted and constrained problems, and include experiments on systems similar to those arising in the Karmarkar algorithm for linear programming. We indicate how recent improvements to the kernel software could greatly improve the performance of the least-squares code.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. P.R. Amestoy and I.S. Duff, Vectorization of a multiprocessor multifrontal code, Report TR 88/3, CERFACS, Toulouse. Report CSS 231, Computer Science and Systems Division, Harwell Laboratory (1988), Int. J. Supercomputer Applics, to appear.

  2. M. Arioli, I.S. Duff and P.P.M. de Rijk, On the augmented systems approach to sparse least-squares problems, Report CSS 223, Computer Science and Systems Division, Harwell Laboratory (1988), Numerische Math., to appear.

  3. R.H. Bartels, G.H. Golub and M.A. Saunders, Numerical techniques in mathematical programming, in:Nonlinear Programming, ed. J.B. Rosen, O.L. Mangasarian and K. Ritter (Academic Press, New York, 1970).

    Google Scholar 

  4. Å. Björck, Iterative refinement of linear least squares solutions, BIT 7(1967)257–278.

    Article  Google Scholar 

  5. Å. Björck, Least squares methods, in:Handbook of Numerical Analysis, Vol. 1.Solution of Equations in R n, ed. P.G. Ciarlet and J.L. Lions (North-Holland, Amsterdam-New York-London, 1987), to appear.

    Google Scholar 

  6. Å. Björck and I.S. Duff, A direct method for the solution of sparse linear least squares problems, Linear Alg. and its Applics. 34(1980)43–67.

    Article  Google Scholar 

  7. I.S. Duff, R.G. Grimes and J.G. Lewis, Sparse matrix test problems, ACM Trans. Math. Softw. 15(1989)1–14.

    Article  Google Scholar 

  8. I.S. Duff and J.K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Softw. 9(1983)302–325.

    Article  Google Scholar 

  9. D.M. Gay, Electronic mail distribution of linear programming test problems, Math. Progr. Soc. COAL Newsletter (1985).

  10. A. George and M.T. Heath, Solution of sparse linear least squares problems using Givens rotations, Linear Alg. and its Applics. 34(1980)69–83.

    Article  Google Scholar 

  11. A. George, M.T. Heath and E. Ng, A comparison of some methods for solving sparse linear least-squares problems, SIAM J. Sci. Stat. Comput. 4(1983)177–187.

    Article  Google Scholar 

  12. G.H. Golub, P. Manneback and Ph.L. Toint, A comparison between some direct and iterative methods for certain large scale geodetic least squares problems, SIAM J. Sci. Stat. Comput. 7(1986)799–816.

    Article  Google Scholar 

  13. G.D. Hachtel, Extended applications of the sparse tableau approach — finite elements and least squares, in:Basic Questions of Design Theory, ed. W.R. Spillers (North-Holland, Amsterdam, 1974).

    Google Scholar 

  14. M.T. Heath, Numerical methods for large sparse linear least squares problems, SIAM J. Sci. Stat. Comput. 5(1984)497–513.

    Article  Google Scholar 

  15. N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica 4(1984)373–395.

    Google Scholar 

  16. C.C. Paige and M.A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw. 8(1982)43–71.

    Article  Google Scholar 

  17. G. Peters and J.H. Wilkinson, The least-squares problem and pseudo-inverses, Computer J. 13(1970)309–316.

    Article  Google Scholar 

  18. M.J.D. Powell and J.K. Reid, On applying Householder transformations to linear least-squares problems, in:Information Processing 68, ed. A.J.H. Morrell (North-Holland, Amsterdam-New York-London, 1969) pp. 122–126.

    Google Scholar 

  19. C.F. Van Loan, On the method of weighting for equality-constrained least-squares problems, SIAM J. Numer. Anal. 22(1985)851–864.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science and Systems Division, Harwell Laboratory, OX11 0RA, Oxon, U.K.

    Iain S. Duff

Authors
  1. Iain S. Duff
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This paper is based on an invited talk by the author at a Workshop on Supercomputers and Large-Scale Optimization held at the Minnesota Supercomputing Center on 16th to 18th May, 1988.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Duff, I.S. The solution of large-scale least-squares problems on supercomputers. Ann Oper Res 22, 241–252 (1990). https://doi.org/10.1007/BF02023055

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02023055

Keywords

Search

Navigation