Аннотация:
В статье приведено полное обоснование модулярного алгоритма приведения к эрмитовой нормальной форме, которое позволило построить новый модулярный алгоритм приведения к смитовой нормальной форме, вычисляющий одновременно и левую матрицу преобразований. Главный член оценки числа операций имеет вид $2(n^3\log D)$, где $n$ — размер, а $D$ — определитель рассматриваемой матрицы (или кратное ему число).
Работа поддержана грантом РФФИ офи м2 13-01-12420.
Ключевые слова:алгоритмы преобразований матриц, нормальные формы матриц, сложность вычислительных алгоритмов.