Рандомизированная численная линейная алгебра: основы и алгоритмы

В этом обзорном исследовании описываются вероятностные алгоритмы для линейно-алгебраических вычислений, таких как факторизация матриц и решение систем линейных уравнений. Основное внимание уделяется методам, эффективность которых подтверждена практикой решения реальных задач. В статье рассматриваются как теоретические основы данной области, так и практические вопросы вычислений. Тематика включает оценивание норм, приближённое представление матриц посредством выборки, структурированные и неструктурированные случайные вложения, задачи линейной регрессии, низкоранговое приближение, итерации по подпространствам и методы Крылова, оценивание погрешности и адаптивность, интерполяционные и CUR-факторизации, приближение Нюстрёма для положительно полуопределённых матриц, алгоритмы с одним представлением («потоковые» алгоритмы), полноранговые факторизации с выявлением ранга, решатели систем линейных уравнений, а также приближение матриц ядер, возникающих в машинном обучении и научных вычислениях.