Náhodné algoritmy se smíšenou přesností

• Název práce v češtině: Náhodné algoritmy se smíšenou přesností
• Název v anglickém jazyce: Mixed Precision Randomized Algorithms
• Klíčová slova: randomized algorithms|numerical linear algebra|matrix computations|finite precision|mixed precision
• Klíčová slova anglicky: randomized algorithms|numerical linear algebra|matrix computations|finite precision|mixed precision
• Akademický rok vypsání: 2024/2025
• Typ práce: disertační práce
• Ústav: Katedra numerické matematiky (32-KNM)
• Vedoucí / školitel: Erin Claire Carson, Ph.D.

Zásady pro vypracování

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

Seznam odborné literatury

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).

Předběžná náplň práce

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.

Předběžná náplň práce v anglickém jazyce

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.