×

zbMATH — the first resource for mathematics

Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices. (English) Zbl 1434.65041

MSC:
65F22 Ill-posedness and regularization problems in numerical linear algebra
15A23 Factorization of matrices
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
65G50 Roundoff error
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[2] R. Car and M. Parrinello, Unified approach for molecular dynamics and density-functional theory, Phys. Rev. Lett., 55 (1985), pp. 2471-2474, https://doi.org/10.1103/PhysRevLett.55.2471.
[3] I. Daubechies, R. DeVore, M. Fornasier, and C. S. Güntürk, Iteratively reweighted least squares minimization for sparse recovery, Comm. Pure Appl. Math., 63 (2010), pp. 1-38. · Zbl 1202.65046
[4] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Softw., 38 (2011), pp. 1:1-1:25, https://doi.org/10.1145/2049662.2049663. · Zbl 1365.65123
[5] J. Demmel, On floating point errors in Cholesky, Tech. Report 14, LAPACK Working Note, 1989.
[6] J. Demmel, L. Grigori, M. Hoemmen, and J. Langou, Communication-optimal parallel and sequential QR and LU factorizations, SIAM J. Sci. Comp, 34 (2012), pp. A206-A239, https://doi.org/10.1137/080731992. · Zbl 1241.65028
[7] T. Fukaya, R. Kannan, Y. Nakatsukasa, Y. Yamamoto, and Y. Yanagisawa, Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices, Preprint, arXiv:1809.11085, 2018, https://arxiv.org/abs/1809.11085.
[8] T. Fukaya, Y. Nakatsukasa, Y. Yanagisawa, and Y. Yamamoto, CholeskyQR \(2\): A simple and communication-avoiding algorithm for computing a tall-skinny QR factorization on a large-scale parallel system, in Proceedings of the 5th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, IEEE Press, 2014, pp. 31-38.
[9] L. Giraud, J. Langou, M. Rozložník, and J. Eshof, Rounding error analysis of the classical gram-schmidt orthogonalization process, Numer. Math., 101 (2005), pp. 87-100. · Zbl 1075.65060
[10] G. H. Golub, V. Loan, and C. F., Matrix Computations, 4th ed., The Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037
[11] N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, 2002. · Zbl 1011.65010
[12] A. Imakura and Y. Yamamoto, Efficient implementations of the modified Gram-Schmidt orthogonalization with a non-standard inner product, Japan Journal of Industrial and Applied Mathematics, 2019, https://doi.org/10.1007/s13160-019-00356-4. · Zbl 1436.65046
[13] R. Kannan, Efficient sparse matrix multiple-vector multiplication using a bitmapped format, in 20th IEEE International Conference on High Performance Computing (HiPC’13), December 2013, pp. 286-294, https://doi.org/10.1109/HiPC.2013.6799135.
[14] R. Kannan, Numerical Linear Algebra problems in Structural Analysis, PhD thesis, School of Mathematics, The University of Manchester, 2014.
[15] B. R. Lowery and J. Langou, Stability analysis of QR factorization in an oblique inner product, Preprint, arXiv:1401.5171, 2014, https://arxiv.org/abs/1401.5171.
[16] M. Mohiyuddin, M. Hoemmen, J. Demmel, and K. Yelick, Minimizing communication in sparse matrix solvers, in Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, SC ’09, New York, NY, USA, 2009, ACM, pp. 36:1-36:12, https://doi.org/10.1145/1654059.1654096.
[17] Multiprecision Computing Toolbox. Advanpix, Tokyo, http://www.advanpix.com.
[18] M. Rozložník, M. Tŭma, A. Smoktunowicz, and J. Kopal, Numerical stability of orthogonalization methods with a non-standard inner product, BIT, (2012), pp. 1-24. · Zbl 1259.65069
[19] S. M. Rump and T. Ogita, Super-fast validated solution of linear systems, J. Comput. Appl. Math., 199 (2007), pp. 199-206. · Zbl 1108.65020
[20] A. Stathopoulos and K. Wu, A block orthogonalization procedure with constant synchronization requirements, SIAM J. Sci. Comp, 23 (2002), pp. 2165-2182. · Zbl 1018.65050
[21] S. Toledo and E. Rabani, Very large electronic structure calculations using an out-of-core filter diagonalization method, J. Comput. Phys., 180 (2002), pp. 256-269. · Zbl 0995.81549
[22] L. N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1997. · Zbl 0874.65013
[23] Y. Yamamoto, Y. Nakatsukasa, Y. Yanagisawa, and T. Fukaya, Roundoff error analysis of the CholeskyQR2 algorihm, Electron. Trans. Numer. Anal, 44 (2015), pp. 306-326. · Zbl 1330.65049
[24] I. Yamazaki, S. Tomov, and J. Dongarra, Mixed-precision Cholesky QR factorization and its case studies on Multicore CPU with Multiple GPUs, SIAM J. Sci. Comput., 37 (2015), pp. C307-C330. · Zbl 1320.65046
[25] Y. Yanagisawa, T. Ogita, and S. Oishi, A modified algorithm for accurate inverse Cholesky factorization, Nonlinear Theory and Its Applications, IEICE, 5 (2014), pp. 35-46. · Zbl 1309.65032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.