Article Sidebar

Submitted
Apr 26, 2017
Published
Apr 1, 2011
Download
PDF
Statistic
Read Counter : 326 Download : 242

Main Article Content

Abstract

After briefly recalling some relevant approaches for preconditioning large symmetric linear systems, we describe a novel class of preconditioners. Our proposal is tailored for large indefinite linear systems, which arise very frequently in many different contexts of numerical analysis and nonlinear optimization. Our preconditioners are built as a byproduct of the Krylov subspace method used to solve the system. We describe theoretical properties of the proposed class of preconditioners, namely their capability of both shifting some eigenvalues of the system’s matrix to controlled values, and reducing the modulus of the other ones. The results of a numerical experimentation give evidence of the good performance of our proposal.

 

 

Keywords

Krylov subspace methods Large indefinite linear systems Large scale optimization Preconditioners Quasi-Newton updates.

Article Details

References

  1. AL-JEIROUDI, G., GONDZIO, J. and HALL, J. 2008. Preconditioning indefinite systems in interior point methods for large scale linear optimization. Optimization Methods and Software, 23: 345–363.
  2. BAGLAMA, J., CALVETTI, D., GOLUB, G. and REICHEL, L. 1998. Adaptively preconditioned GMRES algorithms. SIAM Journal on Scientific Computing, 20: 243–269.
  3. BENZI, M., CULLUM, J. and TUMA, M. 2000. Robust approximate inverse preconditioner for the conjugate gradient method. SIAM Journal on Scientific Computing, 22: 1318–1332.
  4. DENNIS, J. and SCHNABEL, R. 1983. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs.
  5. FASANO, G. 2005. Planar–conjugate gradient algorithm for large–scale unconstrained optimization, Part 1: Theory. Journal of Optimization Theory and Applications, 125: 523–541.
  6. FASANO, G. and ROMA, M. 2007. Iterative computation of negative curvature directions in large scale optimization. Computational Optimization and Applications, 38: 81–104.
  7. FASANO, G. and ROMA, M. 2009. Preconditioning Newton-Krylov methods in nonconvex large scale optimization. Submitted to Computational Optimization and Applications.
  8. FASANO, G. and ROMA, M. 2011a. A class of preconditioners for large indefinite linear systems, as by-product of Krylov-based methods: Part 1. Technical Report n. 4, Department of Management, University Ca’Foscari, Venice, Italy.
  9. FASANO, G. and ROMA, M. 2011b. A class of preconditioners for large indefinite linear systems, as by-product of Krylov-based methods: Part 2. Technical Report n. 5, Department of Management, University Ca’Foscari, Venice, Italy.
  10. GEMAN, S. 1980. A limit theorem for the norm of random matrices. The Annals of Probability, 8: 252–261.
  11. GILL, P.E., MURRAY, W., PONCELEÓN, D.B. and SAUNDERS, M.A. 1992. Preconditioners for indefinite systems arising in optimization. SIAM Journal on Matrix Analysis and Applications, 13: 292–311.
  12. GIRAUD, L. and GRATTON, S. 2006. On the sensitivity of some spectral preconditioners. SIAM Journal on Matrix Analysis and Applications, 27: 1089–1105.
  13. GOLUB, G. and VAN LOAN, C. 1996. Matrix Computations. The John Hopkins Press, Baltimore, Third edition.
  14. GOULD, N.I.M., ORBAN, D. and TOINT, P.L. 2003. CUTEr (and sifdec), a constrained and unconstrained testing environment (revised). ACM Transaction on Mathematical Software, 29: 373–394.
  15. GRATTON, S., SARTENAER, A. and TSHIMANGA, J. 2011. On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides. SIAM Journal on Optimization, 21: 912-935.
  16. HESTENES, M. 1980. Conjugate Direction Methods in Optimization. Springer Verlag, New York.
  17. HIGHAM, N. 2002. Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia, PA, Second edition.
  18. LANCZOS, C. 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral. Journal of Research of the National Bureau of Standards, 45: 255–282.
  19. LUKSAN, L., MATONOHA, C. and VLCEK, J. 2010. Band preconditioners for the matrix free truncated Newton method. Technical Report n. 1079, Institute of Computer Science, Academy of Sciences of the Czech Republic.
  20. MATLAB. 2001. Release 2011a, The MathWorks Inc.
  21. MORALES, J. and NOCEDAL, J. 2000. Automatic preconditioning by limited memory quasi–Newton updating. SIAM Journal on Optimization, 10: 1079–1096.
  22. MORALES, J. and NOCEDAL, J. 2001. Algorithm PREQN: Fortran 77 subroutine for preconditioning the conjugate gradient method. ACM Transaction on Mathematical Software, 27: 83–91.
  23. NASH, S. 1985. Preconditioning of truncated-Newton methods. SIAM J. Scientific and Statistical Computing, 6: 599–616.
  24. NASH, S. 2000. A survey of truncated-Newton methods. Journal of Computational and Applied Mathematics, 124: 45–59.
  25. NOCEDAL, J. and WRIGHT, S. 2000. Numerical Optimization (Springer Series in Operations Research and Financial Engineering) - Second edition, Springer, New York.
  26. PAIGE, C. and SAUNDERS, M. 1975. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12: 617–629.
  27. ROMA, M. 2005. A dynamic scaling based preconditioning for truncated Newton methods in large scale unconstrained optimization. Optimization Methods and Software, 20: 693–713.
  28. SAAD, Y. 2003. Iterative Methods for Sparse Linear Systems. Second Edition, SIAM, Philadelphia.
  29. SIMONCINI, V. and SZYLD, D.B. 2007. Recent developments in Krylov subspace methods for linear systems. Numer. Linear Algebra with Appl., 14: 1–59.
  30. STOER, J. 1983. Solution of large linear systems of equations by conjugate gradient type methods. In Mathematical Programming. The State of the Art, A. BACHEM, M. GRÖTSCHEL, and B. KORTE, eds., Berlin Heidelberg, Springer-Verlag, pp. 540–565.