Вычислить мощность матрицы с целыми числами - PullRequest
Новая
       65

Вычислить мощность матрицы с целыми числами

0 голосов
/ 09 октября 2018

Допустим, у меня есть постоянная матрица A, и я хочу вычислить pow (A, n).Как описано в этом вопросе , я могу вычислить его разложение по собственным значениям (или, в более общем смысле, его инвариантные подпространства и обобщенную модальную матрицу), чтобы ускорить процесс.

Если A является квадратной матрицейразмер k, то алгоритм имеет сложность O (k log n) посредством возведения в степень путем возведения в квадрат и стоимости подготовки (для вычисления модальной матрицы) O (k ^ 3).

Проблема, о которой я думаюэто потеря точности.Вычисление собственных значений и др. Выводит нас из области целых чисел в числа с плавающей запятой.Хотя, в конце концов, мы знаем, что pow (A, n) должен иметь все целочисленные записи, описанный выше алгоритм вычисляет только числа с плавающей запятой.

Другой способ - использовать возведение в степень только путем возведения в квадрат, но это даетмы используем только алгоритм O (k ^ 3 log n).

Есть ли способ, позволяющий точно - без преобразования в числа с плавающей запятой - быстро вычислять pow (A, n)?

Ответы [ 2 ]

0 голосов
/ 28 октября 2018

Используя теорему Кейли-Гамильтона , мы можем быть быстрее.Теорема утверждает, что каждая матричная степень для размерности k может быть записана как сумма первых k степеней A.

Если мы знаем это, мы можем использовать возведение в степень путем возведения в квадрат, но вместоработая с матрицами, мы работаем над полиномами над A с коэффициентами в ℤ.Затем мы можем после каждого шага уменьшить многочлен на характеристический многочлен.

В качестве небольшого примера: 

A = [[1, 1],
     [1, 0]]
A^2 = A + 1 = writing poly. coefficients = {1, 1}

pow(A, 15) = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
           = {1, 0} * ({1, 0} * ({1, 0} * {1, 0}^2)^2)^2
           = {1, 0} * ({1, 0} * ({1, 0} * {1, 0, 0})^2)^2
           = {1, 0} * ({1, 0} * ({1, 0} * {1, 1})^2)^2
           = {1, 0} * ({1, 0} * ({1, 1, 0})^2)^2
           = {1, 0} * ({1, 0} * {2, 1}^2)^2
           = {1, 0} * ({1, 0} * {4, 4, 1})^2
           = {1, 0} * ({1, 0} * {8, 5})^2
           = {1, 0} * ({8, 5, 0})^2
           = {1, 0} * {13, 8}^2
           = {1, 0} * {169, 208, 64}
           = {1, 0} * {377, 233}
           = {377, 233, 0}
           = {610, 377}
           = [[987, 610],
              [610, 377]]

Итак, каковы затраты времени выполнения?Тривиально O(k^2 * log n), потому что на каждом шаге возведения в квадрат нам нужно вычислить квадрат двух полиномов и уменьшить на символ.многочлен.Использование аналогичного трюка с @harold в другом ответе дает O(k log k log n) с использованием умножения дискретных полиномов Фурье, поскольку мы можем найти примитивные корни.

0 голосов
/ 10 октября 2018

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

Поиск нескольких решений полезен, чтобы избежать работы с гигантскими конечными полями, затем вычислите pow (A, n) в некоторых небольших полях и используйте CRT, чтобы определить, каким было бы решение в ℤ.Но для этого нужно каким-то образом иметь достаточное количество полей достаточного размера для работы, и вы не будете заранее знать, что будет достаточно (всегда есть несколько n, над которыми оно перестает работать), так что, возможно, все это не будет работатьна практике.

В качестве небольшого примера возьмем: 

A = [[1, 1],
     [1, 0]]

Характеристика x² - x - 1, давайте предположим, что по модулю 1009 будет работать (это работает), тогда есть корни 383 и627, так: 

A = QDP mod 1009
Q = [[  1,   1],
     [382, 626]]
D = [[383,   0],
     [  0, 627]]
P = [[ 77, 153],
     [933, 856]]

Например, 

pow(A, 15) = Q [[928,   0], P = [[987, 610],
                [  0, 436]]      [610, 377]]

числа Фибоначчи, как и ожидалось, так что все получилось.Но с модулем 1009, значение которого превышает 15 для показателя степени, что делает результат несоответствующим, если бы он был в ℤ, тогда нам потребуется больше / больше полей.

...