Numerical linear algebra

In the field of numerical analysis, numerical linear algebra is an area to study methods to solve problems in linear algebra by numerical computation. The following problems will be considered in this area:

  1. Numerically solving a system of linear equations.
  2. Numerically solving an eigenvalue problem for a given matrix.
  3. Computing approximate values of a matrix-valued function.

Numerical errors can occur in any kind of numerical computation including the area of numerical linear algebra. Errors in numerical linear algebra are considered in another area called "validated numerics".

Latest Studies

Methods for numerical linear algebra has been created by numerical analysts from many generations. But today, some of them have been rejected due to their computation speed or accuracy. Currently, the following methods are widely investigated:

Krylov Subspace Methods

In the field of numerical linear algebra, numerical methods based on the theory of Krylov subspaces are known as Krylov subspaces methods. They are considered to be one of the most successful studies in numerical linear algebra. The next list is the examples of them:

  • MINRES (minimal residual) method
  • CR (conjugate residual) method
  • QMR type methods
    • QMR (quasi minimal residual) method
    • QMR-SYM method
    • TFQMR (transpose free quasi minimal residual) method

Conjugate Gradient Methods

The conjugate gradient (CG) method is one of the best linear equation solving method. It was originally limited to specific linear systems. In order to overcome this difficulty, many kinds of CG variants have benn created:

  • CGS (conjugate gradient squared method)
  • PCG (preconditioned conjugate gradient method)
  • SCG (scaled conjugate gradient)
  • ICCG (incomplete Cholesky conjugate gradient method)
  • COCG (conjugate orthogonal conjugate gradient method)
  • GPBiCG
  • Stabilized methods
    • BiCGSTAB (biconjugate gradient stabilized method)
    • BiCGSTAB2
    • QMRCGSTAB
    • GBi-CGSTAB
  • Block versions (dividing a given matrix into block matrices is a frequently used technique in numerical linear algebra)
    • Block CG
    • Block BiCGSTAB
    • Block BiCGGR
    • Block BiCGGR2
    • Block GWBiCGSTAB

Validated Numerics for Numerical Linear Algebra

While high accuracy and high speed methods in above have been created, some experts have studied how to evaluate numerical errors in numerical linear algebra. The following are their results:

  • Validating numerical solutions of a given system of linear equations
    • Validated numerics for ill-conditioned problems (Ill-conditioned problems are problems which are hard to compute accurately)
    • Pre-conditioning (Pre-conditioning is a procedure to allow the given system of linear equations to be easily solved)
  • Validating numerically obtained eigenvalues
    • Validating numerical solutions of inverse eigenvalue problems (In inverse eigenvalue problems, you will compute and identify an unknown matrix by a given eigenvalue)
  • Rigorously computing determinants
  • Validating numerical solutions of matrix equations
  • Computing matrix functions rigorously (Approximate computation has been studied by N. J. Higham and others)
    • Matrix exponential
    • Matrix logarithm
    • Matrix root

Software

Today, there are many tools for numerical linear algebra. One of the most famous one is MATLAB (matrix laboratory). This was made by MathWorks.

References

  1. 1 2 3 4 5 6 Demmel, J. W. (1997). Applied numerical linear algebra. SIAM.
  2. 1 2 3 4 5 6 Ciarlet, P. G., Miara, B., & Thomas, J. M. (1989). Introduction to numerical linear algebra and optimization. Cambridge University Press.
  3. 1 2 3 4 5 6 Trefethen, Lloyd; Bau III, David (1997). Numerical Linear Algebra (1st ed.). Philadelphia: SIAM.
  4. ↑ Saad, Yousef (2003). Iterative methods for sparse linear systems (2nd ed.). SIAM.
  5. ↑ David S. Watkins (2008), The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM.
  6. ↑ Higham, N. J. (2008). Functions of matrices: theory and computation. SIAM.
  7. 1 2 Rump, S. M. (2010). Verification methods: Rigorous results using floating-point arithmetic. Acta Numerica, 19, 287-449.
  8. ↑ Moler, C. B., & Stewart, G. W. (1973). An algorithm for generalized matrix eigenvalue problems. SIAM Journal on Numerical Analysis, 10(2), 241-256.
  9. ↑ Fernando, K. V., & Parlett, B. N. (1994). Accurate singular values and differential qd algorithms. Numerische Mathematik, 67(2), 191-229.
  10. ↑ U. von Matt, The orthogonal QD algorithm, SIAM J. Sci. Comput., 18 (1997), 1163–1186.
  11. ↑ Araki, S., Kimura, K., Yamamoto, Y., & Nakamura, Y. (2015). Implementation details of an extended oqds algorithm for singular values. JSIAM Letters, 7, 9-12.
  12. ↑ Fast Computation Method of Column Space by using the DQDS Method and the OQDS Method In Proceedings of 2018 International Conference on Parallel and Distributed Processing Techniques and Applications, 333-339, 2018/07, Sho Araki, Hiroki Tanaka, Masami Takata, Kinji Kimura, Yoshimasa Nakamura.
  13. ↑ Dhillon, I. S., Parlett, B. N., & Vömel, C. (2006). The design and implementation of the MRRR algorithm. ACM Transactions on Mathematical Software (TOMS), 32(4), 533-560.
  14. ↑ Abe, K., Zhang, S. L., & Mitsui, T. (1997). MRTR method: An iterative method based on the three-term recurrence formula of CG-type for nonsymmetric matrix. JSIAM, 7, 37-50.
  15. ↑ Sakurai, T., & Sugiura, H. (2003). A projection method for generalized eigenvalue problems using numerical integration. Journal of computational and applied mathematics, 159(1), 119-128.
  16. ↑ Sakurai, T., & Tadano, H. (2007). CIRR: a Rayleigh-Ritz type method with contour integral for generalized eigenvalue problems. Hokkaido mathematical journal, 36(4), 745-757.
  17. ↑ David S. Watkins (2008), The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM.
  18. ↑ Liesen, J., & Strakos, Z. (2012). Krylov subspace methods: principles and analysis. OUP Oxford.
  19. ↑ Christopher C. Paige and Michael A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM Journal on Numerical Analysis 1975; 12(4):617–629.
  20. ↑ Eduard Stiefel, Commentarii Mathematici Helvetici 1952; 29(1):157–179.
  21. ↑ Freund, R. and Nachtigal, N. "QMR: A Quasi-Minimal Residual Method for Non-Hermitian Linear Systems." Numer. Math. 60, 315-339, 1991.
  22. ↑ Freund, R. and Nachtigal, N. "An Implementation of the QMR Method Based on Coupled Two-Term Recurrences." SIAM J. Sci. Statist. Comput. 15, 313-337, 1994.
  23. ↑ R. Freund: Conjugate Gradient-Type Methods for Linear Systems with Complex Symmetric Coefficient Matrices, SIAM Journal on Scientific and Statistical Computing, Vol. 13, No. 1, pp. 425–448 (1992).
  24. ↑ X.-M. Gu, T.-Z. Huang, L. Li, H.-B. Li, T. Sogabe and M. Clemens: Quasi-Minimal Residual Variants of the COCG and COCR Methods for Complex Symmetric Linear Systems in Electromagnetic Simulations, IEEE Transactions on Microwave Theory and Techniques, Vol. 62, No. 12, pp. 2859–2867 (2014).
  25. ↑ Roland W. Freund, A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM Journal on Scientific Computing 1993; 14(2):470–482.
  26. ↑ Hestenes, M. R., & Stiefel, E. (1952). Methods of conjugate gradients for solving linear systems. Washington, DC: NBS.
  27. ↑ Black, Noel and Moore, Shirley. "Conjugate Gradient Squared Method." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/ConjugateGradientSquaredMethod.html
  28. ↑ M. F. Moller. A scaled conjugate gradient algorithm for fast supervised learning. Neural Networks, 6:525--533, 1993.
  29. ↑ H. A. van der Vorst and J. B. M. Melissen: A Petrov-Galerkin type method for solving , where is symmetric complex, IEEE Trans. Mag., Vol. 26, No. 2, pp. 706–708 (1990).
  30. ↑ S. L. Zhang "GPBiCG: Generalized Product-type Methods Based on Bi-CG for Solving Nonsymmetric Linear Systems", SIAM J. Sci. Stat. Comput. , vol.18, no.2, pp.537-551, March 1997.
  31. ↑ Van der Vorst, H. A. (1992). Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM Journal on scientific and Statistical Computing, 13(2), 631-644.
  32. ↑ M. H.Gutknecht，Variants of BiCGSTAB for Matrices with Complex Spectrum，SIAM J. Sci. Statist. Comput.，14(1993)， 1020-1033．
  33. ↑ Tony F. Chan, Efstratios Gallopoulos, Valeria Simoncini, Tedd Szeto and Charles H. Tong, A quasi-minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems, SIAM Journal on Scientific Computing 1994; 15(2):338–347.
  34. ↑ Tanio, M., & Sugihara, M. (2010). GBi-CGSTAB (s, L): IDR (s) with higher-order stabilization polynomials. Journal of Computational and Applied Mathematics, 235(3), 765-784.
  35. ↑ D. P. O’Leary: The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29 (1980), 293–322.
  36. ↑ A. A. Nikishin, A. Yu. Yeremin: Variable block CG algorithms for solving large sparse symmetric positive definite linear systems on parallel computers, I: general iterative methods, SIAM J. Matrix Anal. Appl., 16 (1995), 1135–1153.
  37. ↑ A. El Guennouni, K. Jbilou, H. Sadok: A block version of BiCGSTAB for linear systems with multiple right-hand sides, Electron. Trans. Numer. Anal, 16 (2003), 129–142.
  38. ↑ H. Tadano, T. Sakurai, Y. Kuramashi: Block BiCGGR: a new block Krylov subspace method for computing high accuracy solutions: JSIAM Lett., 1 (2009), 44–47.
  39. ↑ Tadano, H. (2019). Development of the Block BiCGGR2 method for linear systems with multiple right-hand sides. Japan Journal of Industrial and Applied Mathematics, 1-15.
  40. ↑ Tadano, H., & Kuramoto, R. (2019). Accuracy improvement of the Block BiCGSTAB method for linear systems with multiple right-hand sides by group-wise updating technique. Journal of Advanced Simulation in Science and Engineering, 6(1), 100-117.
  41. ↑ Yamamoto, T. (1984). Error bounds for approximate solutions of systems of equations. Japan Journal of Applied Mathematics, 1(1), 157.
  42. ↑ Oishi, S., & Rump, S. M. (2002). Fast verification of solutions of matrix equations. Numerische Mathematik, 90(4), 755-773.
  43. 1 2 Kobayashi, Y., Ogita, T., & Ozaki, K. (2017). Acceleration of a preconditioning method for ill-conditioned dense linear systems by use of a BLAS-based method. Reliable Computing, 25, 15-23.
  44. 1 2 Kobayashi, Y., & Ogita, T. (2016). Accurate and efficient algorithm for solving ill-conditioned linear systems by preconditioning methods. Nonlinear Theory and Its Applications, IEICE, 7(3), 374-385.
  45. 1 2 A fast and efficient algorithm for solving ill-conditioned linear systems (JSIAM Letters Vol.7 (2015) pp.1-4) Yuka Kobayashi, Takeshi Ogita.
  46. ↑ Yamamoto, T. (1980). Error bounds for computed eigenvalues and eigenvectors. Numerische Mathematik, 34(2), 189-199.
  47. ↑ Yamamoto, T. (1982). Error bounds for computed eigenvalues and eigenvectors. II. Numerische Mathematik, 40(2), 201-206.
  48. ↑ Mayer, G. (1994). Result verification for eigenvectors and eigenvalues. Topics in Validated Computations, Elsevier, Amsterdam, 209-276.
  49. ↑ Alefeld, G., Gienger, A., & Mayer, G. (1994). Numerical validation for an inverse matrix eigenvalue problem. Computing, 53(3-4), 311-322.
  50. ↑ Miyajima, S. (2017). Verified Solutions of Inverse Symmetric Eigenvalue Problems. Reliable Computing, 24(1), 31-44.
  51. ↑ Ogita, T. (2008). Verified Numerical Computation of Matrix Determinant. SCAN’2008 El Paso, Texas September 29–October 3, 2008, 86.
  52. ↑ Shinya Miyajima, Verified computation for the Hermitian positive definite solution of the conjugate discrete-time algebraic Riccati equation, Journal of Computational and Applied Mathematics, Volume 350, Pages 80-86, April 2019.
  53. ↑ Shinya Miyajima, Fast verified computation for the minimal nonnegative solution of the nonsymmetric algebraic Riccati equation, Computational and Applied Mathematics, Volume 37, Issue 4, Pages 4599-4610, September 2018.
  54. ↑ Shinya Miyajima, Fast verified computation for the solution of the T-congruence Sylvester equation, Japan Journal of Industrial and Applied Mathematics, Volume 35, Issue 2, Pages 541-551, July 2018.
  55. ↑ Shinya Miyajima, Fast verified computation for the solvent of the quadratic matrix equation, The Electronic Journal of Linear Algebra, Volume 34, Pages 137-151, March 2018
  56. ↑ Shinya Miyajima, Fast verified computation for solutions of algebraic Riccati equations arising in transport theory, Numerical Linear Algebra with Applications, Volume 24, Issue 5, Pages 1-12, October 2017.
  57. ↑ Shinya Miyajima, Fast verified computation for stabilizing solutions of discrete-time algebraic Riccati equations, Journal of Computational and Applied Mathematics, Volume 319, Pages 352-364, August 2017.
  58. ↑ Shinya Miyajima, Fast verified computation for solutions of continuous-time algebraic Riccati equations, Japan Journal of Industrial and Applied Mathematics, Volume 32, Issue 2, Pages 529-544, July 2015.
  59. ↑ Bini, D. A., Higham, N. J., & Meini, B. (2005). Algorithms for the matrix pth root. Numerical Algorithms, 39(4), 349-378.
  60. ↑ Deadman, E., Higham, N. J., & Ralha, R. (2012, June). Blocked Schur algorithms for computing the matrix square root. In International Workshop on Applied Parallel Computing (pp. 171-182). Springer, Berlin, Heidelberg.
  61. ↑ Hargreaves, G. I., & Higham, N. J. (2005). Efficient algorithms for the matrix cosine and sine. Numerical Algorithms, 40(4), 383-400.
  62. ↑ Davies, P. I., & Higham, N. J. (2003). A Schur-Parlett algorithm for computing matrix functions. SIAM Journal on Matrix Analysis and Applications, 25(2), 464-485.
  63. ↑ Miyajima, S. (2019). Verified computation of the matrix exponential. Advances in Computational Mathematics, 45(1), 137-152.
  64. ↑ Miyajima, S. (2019). Verified computation for the matrix principal logarithm. Linear Algebra and its Applications, 569, 38-61.
  65. ↑ Miyajima, S. (2018). Fast verified computation for the matrix principal pth root. Journal of Computational and Applied Mathematics, 330, 276-288.
  66. ↑ Gilat, Amos (2004). MATLAB: An Introduction with Applications 2nd Edition. John Wiley & Sons.
  67. ↑ Quarteroni, Alfio; Saleri, Fausto (2006). Scientific Computing with MATLAB and Octave. Springer.
  68. ↑ Gander, W., & Hrebicek, J. (Eds.). (2011). Solving problems in scientific computing using Maple and Matlab®. Springer Science & Business Media.

Other websites

Further reading