Fast and Accurate Algorithms in Numerical Linear Algebra
| Název práce v češtině: | Rychlé a přesné algoritmy v numerické lineární algebře |
|---|---|
| Název v anglickém jazyce: | Fast and Accurate Algorithms in Numerical Linear Algebra |
| Klíčová slova: | mixed precision|algorithms|numerical linear algebra|finite precision analysis|preconditioning|iterative methods |
| Klíčová slova anglicky: | mixed precision|algorithms|numerical linear algebra|finite precision analysis|preconditioning|iterative methods |
| Akademický rok vypsání: | 2024/2025 |
| Typ práce: | disertační práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra numerické matematiky (32-KNM) |
| Vedoucí / školitel: | doc. Erin Claire Carson, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 09.09.2024 |
| Datum zadání: | 09.09.2024 |
| Datum potvrzení stud. oddělením: | 24.09.2024 |
| Zásady pro vypracování |
| 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 |
| Seznam odborné literatury |
| 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. |
| Předběžná náplň práce |
| 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. |
| Předběžná náplň práce v anglickém jazyce |
| 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. |