References

SOL Software

Some software for linear equations, least squares, and constrained optimization is described here: SOL software

MATLAB Overview

The main matrix factorization (LU, QR, SVD) and many other important features of MATLAB are summarized here: MATLAB Guide, Second Edition by Desmond J. Higham and Nicholas J. Higham, SIAM, 2005.

Texts on Sparse Matrices and Large-Scale Optimization

• T. F. Coleman and Y. Li, eds., Large-Scale Numerical Optimization, SIAM, Philadelphia, 1990.
• A. R. Conn, N. I. M. Gould and Ph. L. Toint, LANCELOT: a Fortran Package for Large-Scale Nonlinear Optimization (Release A), Springer Verlag, Heidelberg, Berlin and New York, 1992.
• W. W. Hager, D. W. Hearn and P. M. Pardalos, eds., Large-Scale Optimization: State of the Art, Kluwer, Dordrecht, 1994.
• G. H. Golub and C. F. Van Loan, Matrix Computations, Third edition, The Johns Hopkins University Press, Baltimore, 1996.
• L. N. Trefethen and D. Bau, III, Numerical Linear Algebra, SIAM, Philadelphia, 1997.
• S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, 1997.
• A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods, SIAM, Philadelphia, 2000.
• See extremely fine review of Trust-Region Methods: Natalia Alexandrov, SIAM Review 45(1), 128-131, 2003.
• R. J. Vanderbei, Linear Programming: Foundations and Extensions, Second edition, Kluwer, Dordrecht, 2001.
• Y. Saad, Iterative Methods for Sparse Linear Systems, Second edition, SIAM, Philadelphia, 2003.
• H. A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, 2003.
• Y. Nesterov, Introductory Lectures on Convex Optimization. Vol. 87. Springer Science & Business Media, 2004.
• T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, 2006.
• J. Nocedal and S. J. Wright, Numerical Optimization, Second Edition, Springer Verlag, New York, 2006.
• F. Bach and R. Jenatton and J. Mairal and G. Obozinski, Optimization with Sparsity-Inducing Penalties, Foundations and Trends in Machine Learning 4(1), 1-106 (2011), DOI: 10.1561/2200000015.
• E. G. Birgin and J. M. Martinez, Practical Augmented Lagrangian Methods for Constrained Optimization, SIAM, Philadelphia, 2014.
• N. Parikh, S. P. Boyd, Proximal Algorithms, Foundations and Trends in Machine Learning (3):123-231, 2014.
• I. S. Duff, A. M. Erisman, and J. K. Reid. Direct Methods for Sparse Matrices, second edition, Oxford University Press, 2017.

Sparse Matrix Methods (Saunders et al.)

• C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Num. Anal. 12, 617-629 (1975).
• C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM TOMS 8(1), 43-71 (1982).
• C. C. Paige and M. A. Saunders, Algorithm 583; LSQR: Sparse linear equations and least-squares problems, ACM TOMS 8(2), 195-209 (1982).
• P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Sparse matrix methods in optimization, SISSC 5, 562-589 (1984).
• P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Maintaining LU factors of a general sparse matrix, LAA 88/89, 239-270 (1987).
• S. K. Eldersveld and M. A. Saunders, A block-LU update for large-scale linear programming, SIMAX 13, 191-201 (1992).
• P. E. Gill, W. Murray, D. B. Ponceleón and M. A. Saunders, Preconditioners for indefinite systems arising in optimization, SIMAX 13, 292-311 (1992).
• M. A. Saunders, Solution of sparse rectangular systems using LSQR and CRAIG, BIT 35, 588-604 (1995).
• P. E. Gill, M. A. Saunders and J. R. Shinnerl, On the stability of Cholesky factorization for quasi-definite systems, SIMAX 17(1), 35-46 (1996).
• M. A. Saunders, Cholesky-based methods for sparse least squares: The benefits of regularization, In L. Adams and J. L. Nazareth (eds.), Linear and Nonlinear Conjugate Gradient-Related Methods, SIAM, Philadelphia, 92-100 (1996).
• A. George and M. A. Saunders, Solution of sparse linear equations using Cholesky factors of augmented systems, Report SOL 99-1, Dept of EESOR, Stanford University (1999), 9 pages. Revised Oct 26, 2000 (draft), 12 pages.
• M. Jacobsen, P. C. Hansen and M. A. Saunders, Subspace preconditioned LSQR for discrete ill-posed problems, BIT 43, 975-989 (2003).
• S.-C. Choi, C. C. Paige and M. A. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput. 33:5, 2950-2971, published electronically Aug 4, 2011.
• D. C.-L. Fong and M. A. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput. 33:5, 2950-2971, published electronically Oct 27, 2011.
• D. C.-L. Fong and M. A. Saunders, CG versus MINRES: An empirical comparison, SQU Journal for Science 17:1, 44-62 (2012).
• D. Ma, L. Yang, R. M. T. Fleming, I. Thiele, B. O. Palsson and M. A. Saunders, Reliable and efficient solution of genome-scale models of Metabolism and macromolecular Expression, Sci. Rep. 7, Article number: 40863 (2017); doi:10.1038/srep40863.

Sparse Matrix Methods (other authors)

• J. K. Reid, A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases, Math. Prog. 24, 55-69, 1982. (Original code LA05 revised as LA15 in HSL 2002.)
• I. S. Duff and J. K. Reid, The design of MA48: a code for the direct solution of sparse unsymmetric linear systems of equations, ACM TOMS 22(2), 187-226, 1996. (abstract)
• A. Gupta, Recent advances in direct methods for solving unsymmetric sparse systems of linear equations, ACM TOMS 28(3), 301-324, 2002. (abstract)
• L. Bergamaschi, J. Gondzio, and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization, Report MS-02-002, Dept of Mathematics and Statistics, The University of Edinburgh, July 26, 2002, revised March 18, 2003. (PS file)
• I. S. Duff, MA57 - A new code for the solution of sparse symmetric definite and indefinite systems, ACM TOMS 30(2), 118-144, 2004. (Abstract, BibTex entry)
• T. Davis, UMFPACK.
• M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle-point problems, Acta Numerica 2005, Cambridge University Press, 1-137 (2005).
• G. H. Golub, C. Greif, and J. M. Varah, An algebraic analysis of a block diagonal preconditioner for saddle point systems, SIAM J. Matrix Analysis and Applics. 27(3), 779-792 (2006). (SIAM archive)
• S.-C. Choi, Iterative Methods for Singular Linear Equations and Least-Squares Problems, PhD thesis, ICME, Stanford University (2006).
• H. M. Huynh, A Large-scale Quadratic Programming Solver Based on Block-LU Updates of the KKT System, PhD thesis, ICME, Stanford University (2008).
• Ghussoun Al-Jeiroudi, Jacek Gondzio, and Julian Hall, Preconditioning indefinite systems in interior point methods for large scale linear optimisation, Optimization Methods and Software 23:3 (2008) 345-363.
• C. M. Maes, A Regularized Active-set Method for Sparse Convex Quadratic Programming, PhD thesis, Stanford University (2010).
• D. C.-L. Fong, Minimum-Residual Methods for Sparse Least-Squares Using Golub-Kahan Bidiagonalization, PhD thesis, Stanford University (2011).

Optimization Methods (Saunders et al.)

• B. A. Murtagh and M. A. Saunders, Large-scale linearly constrained optimization, Math. Prog. 14, 41-72 (1978).
• B. A. Murtagh and M. A. Saunders, A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints, Math. Prog. Study 16 (Constrained Optimization), 84-117 (1982).
• P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin and M. H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Prog. 36, 183-209 (1986).
• M. A. Saunders, Major Cholesky would feel proud, ORSA J. on Computing 6, 23-27 (1994).
• M. A. Saunders and J. A. Tomlin, Solving regularized linear programs using barrier methods and KKT systems, Report SOL 96-4, Dept of EESOR, Stanford University (1996).
• S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by Basis Pursuit, SIAM Review 43(1), 129-159 (2001). (SIAM archive)
• P. E. Gill, W. Murray and M. A. Saunders, SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM Review 47(1), 99-131, 2005. (SIAM archive) (SIGEST Introduction)
• M. P. Friedlander and M. A. Saunders, A globally convergent LCL method for nonlinear optimization, SIAM J. Optim. 15(3), 863-897 (2005).
• R. Tibshirani, M. A. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused lasso, J. Royal Statistical Society B 67(1), 91-108 (2005).
• M. W. Carter, H. H. Jin, M. A. Saunders, and Y. Ye. SpaseLoc: An adaptive subproblem algorithm for scalable wireless sensor network localization, SIAM J. on Optimization 17(4), 1102-1128 (2006).
• S.-C. T. Choi, C. C. Paige and M. A. Saunders. MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, SIAM J. Sci. Comput. 33:4, 1810-1836 (2011).
• D. C.-L. Fong and M. A. Saunders. LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput. 33:5, 2950-2971 (2011).
• D. C.-L. Fong and M. A. Saunders. CG versus MINRES: An empirical comparison, SQU Journal for Science 17:1, 44-62 (2012).

Optimization Methods (other authors)

• R. E. Bixby, Solving real-world linear programs: a decade and more of progress, Operations Research 50(1), 3-15, 2002.
• Jiming Peng, Cornelis Roos and Tamas Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton, NJ, 2002.
• E. M. Gertz and S. J. Wright, Object-oriented software for quadratic programming, ACM TOMS 29(1), 58-81, 2003.
• N. I. M. Gould, D. Orban and Ph. L. Toint, GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM TOMS 29(4), 353-372, 2003. (current reports)
• SIAG/OPT View-and-News, 14(1), April 2003. Special issue on Large Scale Nonconvex Optimization. (View on-line)
• N. I. M. Gould, D. Orban and Ph. L. Toint, Numerical methods for large-scale nonlinear optimization, Acta Numerica 2005, Cambridge University Press, 299-361, 2005. (current reports)
• Michael Friedlander's homepage refers to some excellent papers and software.
• Dominique Orban's homepage refers to more excellent papers and software.
• Stephen Becker's software.