On Tuesday, 31 March 2026 at 06:24:02 UTC-7 Georgi Guninski wrote:
Matrix power M^m can be computed in O(n^3 \log_2(m)) with repeated squaring. Matrix power D^m of an n x n diagonal matrix can be computed in O(n log_2(m)) multiplications. The diagonalization of an n x n matrix has a cost independent of m , so computing M^m as P^(-1)*D^m*P for a diagonalizable matrix M can be way cheaper. It depends a bit on what you want to optimize for, but generally for constant size n and growing m, you can get a much nicer constant (wrt. m) by diagonalizing. If you need to take a field extension to get a diagonal matrix, the cost of your multiplications may go up a bit, eating up some of the difference between the n and the n^3. If your matrix isn't quite diagonalizable, you may end up having to take a power of your JNF to make it diagonal, but for m>>n that will be a "small" power. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/sage-devel/dc0f6829-54b2-462d-ac8e-314d8448759dn%40googlegroups.com.
