ГлавнаяАрхивО реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа

О реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа | Прикладная дискретная математика. 2013. № 3(21).

Рассматривается задача реализации алгоритма Копперсмита, вычисляющего векторные аннулирующие многочлены для матричных последовательностей, на современных 64-разрядных ЭВМ. Рассмотрены вопросы представления данных для случая последовательностей бинарных матриц с точки зрения снижения трудоёмкости алгоритма. Предложены способы эффективного распараллеливания алгоритма для реализации на ЭВМ с многоядерными процессорами, а также для выполнения алгоритма на вычислителях кластерного типа.
  • Title О реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа
  • Headline О реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(21)
  • Date:
  • DOI
Ключевые слова
matrix sequences, Coppersmith algorithm, матричные последовательности, алгоритм Копперсмита
Авторы
Ссылки
Coppersmith D. Fast evaluation of logarithms in fields of characteristic two // IEEE Trans. Inform. Theory. 1984. V.IT-30(4). P. 587-594.
Montgomery P. L. A block Lanczos algorithm for finding dependencies over GF(2) // EUROCRYPT'95. LNCS. 1995. V.921. P. 106-120.
Coppersmith D. Solving linear equations over GF(2) via block Wiedemann algorithm // Math. Comp. 1994. No. 62(205). P. 333-350.
Wiedemann D. H. Solving sparse linear equations over finite fields // IEEE Trans. Inform. Theory. 1986. V.IT-32(1). P. 54-62.
Thome E. Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm // J. Symbolic Comput. 2002. No. 33. P. 757-775.
Ахо А., Хопкрофт Д., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.
Beckerman B. and Labahn G. A uniform approach for the fast computation of matrix-type Pade approximants // SIAM J. Matrix Anal. Appl. 1994. No. 15(3). P. 804-823.
О реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа | Прикладная дискретная математика. 2013. № 3(21).
О реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа | Прикладная дискретная математика. 2013. № 3(21).
Полнотекстовая версия