Náhodné algoritmy se smíšenou přesností
| Thesis title in Czech: | Náhodné algoritmy se smíšenou přesností |
|---|---|
| Thesis title in English: | Mixed Precision Randomized Algorithms |
| Key words: | randomized algorithms|numerical linear algebra|matrix computations|finite precision|mixed precision |
| English key words: | randomized algorithms|numerical linear algebra|matrix computations|finite precision|mixed precision |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | dissertation |
| Thesis language: | |
| Department: | Department of Numerical Mathematics (32-KNM) |
| Supervisor: | Erin Claire Carson, Ph.D. |
| Author: |
| Guidelines |
| The last decade has seen exciting work on the use of randomization in matrix computations and numerical linear algebra. The potential benefits of randomized algorithms include faster runtime, better stability, and a greater level of interpretability. There is deep theory underlying randomized numerical linear algebra and there has been significant work
in analyzing how much approximation error is introduced through randomized sketching and how this affects solutions. However, nearly ubiquitously, inexactness due to finite precision computation is not taken into account in such analyses. This is both dangerous from a viewpoint of understanding the limitations of these methods, but also results in missed opportunities; our intuition says that in many cases, we can likely use low precision selectively within randomized algorithms to improve performance. This thesis will involve: * The development of new randomized algorithms, e.g., randomized preconditioners for saddle point problems, and randomized algorithms for variants of least squares problems * Analysis of new and existing randomized algorithms, accounting for both error due to approximation/randomization and finite precision errors * Development of mixed precision implementations based on insights from analysis * Implementations and numerical/performance experiments |
| References |
| P. Drineas and M. W. Mahoney, RandNLA: Randomized numerical linear algebra, Communications of
the ACM, 59 (2016), pp. 80–90. N. Halko, P.-G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM review, 53 (2011), pp. 217–288. P.-G. Martinsson and J. Tropp, Randomized numerical linear algebra: Foundations and algorithms, Acta Numerica, 29 (2020), pp. 403–572. Y. Nakatsukasa and J. A. Tropp, Fast & accurate randomized algorithms for linear systems and eigenvalue problems, arXiv preprint arXiv:2111.00113, (2021). P. Xie, H. Xiang, and Y. Wei, Randomized algorithms for total least squares problems, Numerical Linear Algebra with Applications, 26 (2019), p. e2219. N. J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, second ed., 2002. Connolly, Michael P., Nicholas J. Higham, and Srikara Pranesh. "Randomized Low Rank Matrix Approximation: Rounding Error Analysis and a Mixed Precision Algorithm." (2022). |
| Preliminary scope of work |
| The last decade has seen exciting work on the use of randomization in matrix computations and numerical linear algebra. The potential benefits of randomized algorithms include faster runtime, better stability, and a greater level of interpretability. This thesis will study how we can combine mixed precision computations and randomized approaches to obtain fast, high-performance algorithms. |
| Preliminary scope of work in English |
| The last decade has seen exciting work on the use of randomization in matrix computations and numerical linear algebra. The potential benefits of randomized algorithms include faster runtime, better stability, and a greater level of interpretability. This thesis will study how we can combine mixed precision computations and randomized approaches to obtain fast, high-performance algorithms. |