Algorithm 937: MINRES-QLP for Symmetric and Hermitian Linear Equations and Least-Squares Problems

Area of Science:

• Numerical Analysis
• Scientific Computing
• Linear Algebra

Background:

• The MINRES algorithm is used for solving symmetric or Hermitian linear systems and least-squares problems.
• The standard MINRES algorithm can face instability and does not provide minimum-length solutions for singular systems.

Purpose of the Study:

• To introduce the MINRES-QLP algorithm and its FORTRAN 90 implementation.
• To address limitations of the original MINRES algorithm, specifically regarding singular systems and potential instability.
• To provide a secure and efficient implementation for solving linear systems and least-squares problems.

Main Methods:

• Development of the MINRES-QLP algorithm, an enhancement of the MINRES algorithm.
• Implementation of MINRES-QLP in FORTRAN 90, featuring a design pattern for secure data handling and avoiding reverse communication.
• Utilizing Matrix Market format for inputting test problems.
• Providing MATLAB versions for broader accessibility.

Main Results:

• MINRES-QLP successfully computes the unique minimum-length (pseudoinverse) solution for singular systems.
• The algorithm overcomes potential instabilities present in the original MINRES.
• The FORTRAN 90 implementation demonstrates a secure design pattern, enhancing usability.
• Test programs successfully solve real and complex problems.

Conclusions:

• MINRES-QLP offers a robust and stable solution for symmetric/Hermitian linear systems and least-squares problems, including singular cases.
• The FORTRAN 90 implementation provides a secure and efficient tool for scientific computing.
• The algorithm and its implementations are valuable for researchers and practitioners in numerical analysis and scientific computing.