Блокировать алгоритм Ланцоша

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

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

и очень похож на него . Он основан на алгоритме Ланцоша для поиска собственных значений больших разреженных действительных матриц

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

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

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