Sparse Direct Methods: An Introduction

  • J. A. Scott
Conference paper
Part of the Lecture Notes in Physics book series (LNP, volume 535)


The solution of large-scale linear systems lies at the heart of many computations in science, engineering, industry, and (more recently) finance. In this paper, we give a brief introduction to direct methods based on Gaussian elimination for the solution of such systems. We discuss the methods with reference to the sparse direct solvers that are available in the Harwell Subroutine Library. We briefly consider large sparse eigenvalue problems and show how the efficient solution of such problems depends upon the efficient solution of sparse linear systems.


Gaussian Elimination Sparsity Pattern Sparse Linear System Rutherford Appleton Laboratory Innermost Loop 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Harw ell Subroutine Library, A Catalogue of Subroutines (Release 12), Advanced Computing Department, AEA Technology, Harwell Laboratory, Oxfordshire, England (1996).Google Scholar
  2. 2.
    I.S. Duff, A.M. Erisman, and J.K. Reid, Direct Methods for Sparse Matrices, Oxford University Press, England (1986).zbMATHGoogle Scholar
  3. 3.
    I.S. Duff, in The State of the Art in Numerical Analysis, I.S. Duff and G.A. Watson, eds., Oxford University Press, England (1997).Google Scholar
  4. 4.
    I. S. Duff, Technical Report, RAL-TR-1998-054, Rutherford Appleton Laboratory (1998).Google Scholar
  5. 5.
    I.S. Duff, R.G. Grimes, and J.G. Lewis, Technical Report, RAL-TR-92-086, Rutherford Appleton Laboratory (1992).Google Scholar
  6. 6.
    H. M. Markowitz, Management Science, 3, 255 (1957).zbMATHMathSciNetGoogle Scholar
  7. 7.
    I.S. Duff and J.K Reid, ACM Trans.Math.Soft., 22, 187 (1996).zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    J.J. Dongarra, J. DuCroz, I.S. Duff, and S. Hammarling, ACM Trans.Math.Soft., 16, 1 (1990).zbMATHCrossRefGoogle Scholar
  9. 9.
    I. S. Duff, Report AERE R10079, Her Majesty’s Stationery Office, London (1981).Google Scholar
  10. 10.
    I.S. Duff and J.A. Scott, ACM Trans.Math.Soft., 22, 30 (1996).zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    I.S. Duff and J.A. Scott, Technical Report RAL-TR-97-012, Rutherford Appleton Laboratory (1997).Google Scholar
  12. 12.
    J.K. Reid and J.A. Scott, Technical Report RAL-TR-98-016, Rutherford Appleton Laboratory (1998).Google Scholar
  13. 13.
    J. A. Scott, Technical Report RAL-TR-1998-031, Rutherford Appleton Laboratory (1998).Google Scholar
  14. 14.
    J. A. Scott, Technical Report RAL-TR-1998-056, Rutherford Appleton Laboratory (1998).Google Scholar
  15. 15.
    I.S. Duff and J.A. Scott, in Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, J.G. Lewis, ed., SIAM, Philadelphia (1994).Google Scholar
  16. 16.
    I.S. Duff, and J. Koster, Technical Report RAL-TR-97-059, Rutherford Appleton Laboratory (1997).Google Scholar
  17. 17.
    P.R. Amestoy and I.S. Duff, Inter. J. of Supercomputer Applics, 3, 41 (1989).CrossRefGoogle Scholar
  18. 18.
    A.C Damhaug and J.K. Reid, Technical Report RAL-TR-96-10, Rutherford Appleton Laboratory (1996).Google Scholar
  19. 19.
    T.A. Davis and I.S. Duff, SIAM J.Matrix Analysis and Applics, 18, 140 (1997).zbMATHCrossRefMathSciNetGoogle Scholar
  20. 20.
    I.S. Duff and J.A. Scott, Technical Report RAL-TR-96-102 (revised), Rutherford Appleton Laboratory (1996).Google Scholar
  21. 21.
    A. Erisman and W.F. Tinney, Communications ACM 18, 177 (1975).zbMATHCrossRefMathSciNetGoogle Scholar
  22. 22.
    Y. Saad, Numerical Methods for Large Eigenvalue Problems, Halsted Press (1992).Google Scholar
  23. 23.
    I.S. Duff and J.A. Scott, ACM Trans.Math.Soft., 19, 137 (1993).zbMATHCrossRefMathSciNetGoogle Scholar
  24. 24.
    J.A. Scott, ACM Trans.Math.Soft., 21, 432 (1995).zbMATHCrossRefGoogle Scholar
  25. 25.
    R.B. Lehoucq, D.C. Sorensen and C. Yang, ARPACK USERS GUIDE: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM, Philadelphia, PA (1998).Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1999

Authors and Affiliations

  • J. A. Scott
    • 1
  1. 1.Department for Computation and InformationRutherford Appleton LaboratoryOxonEngland

Personalised recommendations