Cache-friendly, low-memory Lanczos algorithm in Rust
Стандартный алгоритм Ланцоса для вычисления матричных функций требует значительных ресурсов памяти: хранение n×k базисной матрицы, которая растёт с каждой итерацией. Для задачи с 500 000 переменными и 1000 итерациями это около 4 ГБ только для базиса. В статье представлен двухпроходной вариант алгоритма, требующий всего O(n) памяти ценой удвоения числа матрично-векторных произведений. При грамотной реализации этот подход не только экономит память, но и может работать быстрее для определённых задач.
Автор подробно описывает реализацию на Rust, включая шаги рекуррентного вычисления, итератор для управления состоянием, первый проход (вычисление разложения) и второй проход (восстановление решения). Интересно, что теоретические ожидания производительности не всегда подтверждаются на практике, особенно для средних по размеру матриц. Весь код доступен на GitHub, а технический отчёт с доказательствами и дополнительными экспериментами можно скачать отдельно.