0

I am trying to implement a Matrix.pow(int exp) method for exp >= 0.
My current implementation repeatedly calls a Matrix.mul(Matrix m) method, which works well for small exponent.

For large exponents, however, the solution becomes skewed. The Matrix class is using doubles internally and I think that the repeated calls end up in a loss of precision.

I was looking at http://en.wikipedia.org/wiki/Exponentiation_by_squaring, which will certainly help, but I think it will still be an issue for larger exponents.

Is there a better way to exponentiate a Matrix?

AJ.
  • 4,526
  • 5
  • 29
  • 41
Xandaros
  • 645
  • 1
  • 6
  • 17
  • So the algorithm is correct from an algebraic perspective but is numerically too inexact? – Codor Jun 03 '14 at 08:32
  • 1
    Perhaps you might use BigDecimal instead of doubles? – MightyPork Jun 03 '14 at 08:34
  • see the expm function in jblas: https://github.com/mikiobraun/jblas/blob/master/src/main/java/org/jblas/MatrixFunctions.java, or use jblas. – perreal Jun 03 '14 at 08:36
  • possible duplicate of [Fast Matrix Exponentiation](http://stackoverflow.com/questions/12311869/fast-matrix-exponentiation) – Erwin Bolwidt Jun 03 '14 at 09:30
  • @ErwinBolwidt This question is about numerical stability, not speed. These goals usually have different solutions. Consider a matrix product chain: to maximize speed you multiply along the shortest dimensions first, but to maximize stability you use the long dimensions. – crockeea Jun 03 '14 at 13:35
  • @Eric if you improve speed by reducing the number of intermediate calculations (like here), it may also achieve less of an error caused by loss of precision. As there is no sample code in the question, it's hard to compare the errors in the output but I have a strong hunch that the accepted answer to my duplicate has a smaller error in the output. – Erwin Bolwidt Jun 03 '14 at 14:11
  • 1
    @Xandaros You realize that exponentiation by squaring has O(log(n)) complexity? Your exponent would have to be ludicrously huge to get the same stability problems as naive matrix multiplication. Have you tried implementing it yet? I think it will probably do the trick for you. – crockeea Jun 03 '14 at 14:31

2 Answers2

1

Think to use BigDecimal instead of double , if you are using a java api make sure that the method that you are using use BigDecimal instead of Double.you could use an open source project and edit it like these one here.

oussama.elhadri
  • 738
  • 3
  • 11
  • 27
1

In most cases repeated squares is the best solution for your problem. Try it out, the accuracy is way better than with repeated multiplication. If the accuracy is still not sufficient there are ways to improve the numerical stability depending on the type of matrix. E.g. if you have a symmetric matrix you can diagonalize upfront and calculate the power of the Eigenvalues. That way a singular matrix remains singular. There are other methods for other special types of matrices, I can elaborate on that if you tell us what sort of matrices you have.

pentadecagon
  • 4,717
  • 2
  • 18
  • 26