Точность потенции матрицы

Я пытаюсь реализовать метод Matrix.pow(int exp) для exp >= 0.
Моя текущая реализация постоянно вызывает метод Matrix.mul(Matrix m), который хорошо работает для малых показателей.

Однако для больших показателей решение становится искаженным. Класс Matrix использует двойники внутри, и я думаю, что повторные вызовы заканчиваются потерей точности.

Я просматривал http://en.wikipedia.org/wiki/Exponentiation_by_squaring, который, безусловно, помочь, но я думаю, что это все еще будет проблемой для более крупных экспонентов.

Есть ли лучший способ возвести в степень матрицу?


java matrix math
person Xandaros    schedule 03.06.2014    source источник
comment
Значит, алгоритм верен с алгебраической точки зрения, но слишком неточен в числовом отношении?   -  person Codor    schedule 03.06.2014
comment
Возможно, вы могли бы использовать BigDecimal вместо удвоения?   -  person MightyPork    schedule 03.06.2014
comment
см. функцию expm в jblas: github .com/mikiobraun/jblas/blob/master/src/main/java/org/jblas/ или используйте jblas.   -  person perreal    schedule 03.06.2014
comment
возможный дубликат быстрого матричного возведения в степень   -  person Erwin Bolwidt    schedule 03.06.2014
comment
@ErwinBolwidt Этот вопрос касается численной стабильности, а не скорости. Эти цели обычно имеют разные решения. Рассмотрим цепочку матричных продуктов: чтобы максимизировать скорость, вы сначала умножаете самые короткие измерения, но чтобы максимизировать стабильность, вы используете длинные измерения.   -  person crockeea    schedule 03.06.2014
comment
@Eric, если вы улучшите скорость за счет уменьшения количества промежуточных вычислений (как здесь), это также может привести к уменьшению количества ошибок, вызванных потерей точности. Поскольку в вопросе нет примера кода, трудно сравнивать ошибки в выводе, но у меня есть сильное подозрение, что принятый ответ на мой дубликат имеет меньшую ошибку в выводе.   -  person Erwin Bolwidt    schedule 03.06.2014
comment
@Xandaros Вы понимаете, что возведение в степень путем возведения в квадрат имеет сложность O (log (n))? Ваш показатель степени должен быть смехотворно огромным, чтобы получить те же проблемы со стабильностью, что и наивное матричное умножение. Вы уже пробовали его реализовать? Я думаю, что это, вероятно, поможет вам.   -  person crockeea    schedule 03.06.2014

Ответы (2)


arrow_upward
1
arrow_downward

Подумайте об использовании BigDecimal вместо double , если вы используете java API, убедитесь, что метод, который вы используете, использует BigDecimal вместо Double. Вы можете использовать проект с открытым исходным кодом и редактировать его, как этот здесь.

person oussama.elhadri    schedule 03.06.2014

arrow_upward
1
arrow_downward

В большинстве случаев повторяющиеся квадраты — лучшее решение вашей проблемы. Попробуйте, точность намного лучше, чем при многократном умножении. Если точность по-прежнему недостаточна, существуют способы улучшить числовую стабильность в зависимости от типа матрицы. Например. если у вас есть симметричная матрица, вы можете заранее диагонализовать и вычислить мощность собственных значений. Таким образом, сингулярная матрица остается сингулярной. Существуют и другие методы для других специальных типов матриц, я могу рассказать об этом, если вы сообщите нам, какие у вас матрицы.

person pentadecagon    schedule 03.06.2014