Алгоритм блочного Ланцоша
В информатике блочный алгоритм Ланцоша — это алгоритм для нахождения нулевого пространства матрицы над конечным полем , использующий только умножение матрицы на длинные тонкие матрицы. Такие матрицы рассматриваются как векторы кортежей записей конечного поля, и поэтому их обычно называют «векторами» в описаниях алгоритма.
Алгоритм блочного Ланцоша является одним из наиболее эффективных известных методов поиска нулевых пространств, что является заключительным этапом в алгоритмах целочисленной факторизации, таких как квадратичное решето и решето числового поля , и его разработка полностью обусловлена этим приложением.
Он основан на алгоритме Ланцоша для нахождения собственных значений больших разреженных действительных матриц и имеет на него большое сходство. [1]
Проблемы распараллеливания
Алгоритм по сути не является параллельным: конечно, можно распределить умножение матрицы на «вектор», но весь вектор должен быть доступен для шага объединения в конце каждой итерации, поэтому все машины, участвующие в вычислении, должны быть в одной и той же быстрой сети. В частности, невозможно расширять векторы и распределять срезы векторов по разным независимым машинам.
Блочный алгоритм Видемана более полезен в контекстах, где доступно несколько систем, каждая из которых достаточно велика, чтобы вместить всю матрицу, поскольку в этом алгоритме системы могут работать независимо до конечной стадии в конце.
Ссылки
- ^ Монтгомери, ПЛ (1995). "Блочный алгоритм Ланцоша для поиска зависимостей по GF(2)". Конспект лекций по информатике . EUROCRYPT '95. Том 921. Springer-Verlag. С. 106–120. doi : 10.1007/3-540-49264-X_9 .
 | Эта статья по линейной алгебре — заглушка . Вы можете помочь Википедии, расширив ее. |
