Fast and Accurate Algorithms in Numerical Linear Algebra
| Thesis title in Czech: | Rychlé a přesné algoritmy v numerické lineární algebře |
|---|---|
| Thesis title in English: | Fast and Accurate Algorithms in Numerical Linear Algebra |
| Key words: | mixed precision|algorithms|numerical linear algebra|finite precision analysis|preconditioning|iterative methods |
| English key words: | mixed precision|algorithms|numerical linear algebra|finite precision analysis|preconditioning|iterative methods |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | dissertation |
| Thesis language: | angličtina |
| Department: | Department of Numerical Mathematics (32-KNM) |
| Supervisor: | doc. Erin Claire Carson, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 09.09.2024 |
| Date of assignment: | 09.09.2024 |
| Confirmed by Study dept. on: | 24.09.2024 |
| Guidelines |
| This thesis will involve investigating the effect of the use of low and mixed precision in storage and computations with hierarchical matrices, which arise diverse application areas from PDEs to machine learning. The thesis will involve the following:
* Rigorously proving that low-rank off-diagonal blocks of the matrix can be stored and/or computed in low precision without detriment to accuracy of subsequent computations (e.g., in hierarchical Cholesky factorization, or as preconditioners in Krylov subspace methods). This involves treating both deterministic and randomized approaches to low-rank approximation of pieces of the matrix, and may involve various particular hierarchical structures (e.g., H matrices, H^2 matrices, HSS matrices, etc.) * Design of mixed precision algorithms involving hierarchical matrices * Parallel implementation and evaluation on large-scale machines * Application of the results to particular scientific application areas |
| References |
| M. Bebendorf, Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems,
vol. 63 of Lecture Notes in Computer Science and Engineering, Springer-Verlag Berlin Heidelberg, 2008. S. Börm, L. Grasedyck, and W. Hackbusch, Introduction to hierarchical matrices with applications, Engineering analysis with boundary elements, 27 (2003), pp. 405–422. P. Ghysels, S. L. Xiaoye, C. Gorman, and F.-H. Rouet, A robust parallel preconditioner for indefinite systems using hierarchical matrices and randomized sampling, in Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2017, pp. 897–906. N. J. Higham and T. Mary, Solving block low-rank linear systems by LU factorization is numerically stable, MIMS EPrint 2019.15, Manchester Institute for Mathematical Sciences, The University of Manchester, 2019. J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Fast algorithms for hierarchically semiseparable matrices, Numerical Linear Algebra with Applications, 17 (2010), pp. 953–976. Keyes, David E., Hatem Ltaief, and George Turkiyyah. "Hierarchical algorithms on hierarchical architectures." Philosophical Transactions of the royal society A 378.2166 (2020): 20190055. Abdulah, Sameh, et al. "Accelerating geostatistical modeling and prediction with mixed-precision computations: A high-productivity approach with parsec." IEEE Transactions on Parallel and Distributed Systems 33.4 (2021): 964-976. Martinsson, Per-Gunnar. "A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix." SIAM Journal on Matrix Analysis and Applications 32.4 (2011): 1251-1274. Higham, Nicholas J. Accuracy and stability of numerical algorithms. Society for industrial and applied mathematics, 2002. |
| Preliminary scope of work |
| So-called hierarchical matrices arise in a number of application areas, from PDEs to machine learning. A key aspect of this structure is that subblocks of the matrix are represented by low-rank components, which significantly reduces the cost of storing and computing with such matrices. Intuition indicates that if we are using low-rank approximations of some pieces of the matrix, these can likely be stored and computed in low precision as well to further improve performance without affecting the accuracy of downstream computations. This thesis will involve rigorously proving this, designing mixed precision algorithms for hierarchical matrices, and developing high performance implementations. |
| Preliminary scope of work in English |
| So-called hierarchical matrices arise in a number of application areas, from PDEs to machine learning. A key aspect of this structure is that subblocks of the matrix are represented by low-rank components, which significantly reduces the cost of storing and computing with such matrices. Intuition indicates that if we are using low-rank approximations of some pieces of the matrix, these can likely be stored and computed in low precision as well to further improve performance without affecting the accuracy of downstream computations. This thesis will involve rigorously proving this, designing mixed precision algorithms for hierarchical matrices, and developing high performance implementations. |