Блочный алгоритм Ланцоша - Block Lanczos algorithm

В Информатика, то блочный алгоритм Ланцоша является алгоритм для поиска пустое пространство из матрица через конечное поле, используя только умножение матрицы на длинные тонкие матрицы. Такие матрицы рассматриваются как векторы кортежи элементов с конечным полем, и поэтому в описании алгоритма их принято называть «векторами».

Блочный алгоритм Ланцоша является одним из наиболее эффективных методов, известных для поиска нулевых пространств, что является заключительным этапом в целочисленная факторизация алгоритмы, такие как квадратное сито и числовое поле сито, и его разработка была полностью обусловлена ​​этим приложением.

Проблемы с распараллеливанием

По сути, алгоритм не является параллельным: конечно, можно распределить умножение «матрица-вектор», но весь вектор должен быть доступен для этапа комбинирования в конце каждой итерации, поэтому все машины, участвующие в вычислении, должны быть в той же быстрой сети. В частности, невозможно расширить векторы и распределить срезы векторов на разные независимые машины.

В блочный алгоритм Видемана более полезен в контекстах, где доступно несколько систем, каждая из которых достаточно велика, чтобы вместить всю матрицу, поскольку в этом алгоритме системы могут работать независимо до заключительного этапа в конце.

История

Блочный алгоритм Ланцоша был разработан Питер Монтгомери и опубликовано в 1995 г .;^[1] он основан на и очень похож на Алгоритм Ланцоша для поиска собственные значения больших разреженных вещественных матриц.

Рекомендации

1. Монтгомери, П. Л. (1995). «Блочный алгоритм Ланцоша для поиска зависимостей по GF (2)». Конспект лекций по информатике. ЕВРОКРИПТ '95. 921. Springer-Verlag. С. 106–120. Дои:10.1007 / 3-540-49264-X_9.