commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mikkel Meyer Andersen (JIRA)" <j...@apache.org>
Subject [jira] Created: (MATH-435) Efficient matrix power
Date Mon, 08 Nov 2010 22:26:25 GMT
Efficient matrix power
----------------------

                 Key: MATH-435
                 URL: https://issues.apache.org/jira/browse/MATH-435
             Project: Commons Math
          Issue Type: Improvement
            Reporter: Mikkel Meyer Andersen
            Assignee: Mikkel Meyer Andersen


For symmetric matrices A it is easy to find A^n also for large n by making an eigenvalue/-vector
decomposition.

In general, if the structure of the matrix is not know and the n'th power is needed, A*A*...*A
is way too inefficient. By using a binary representation and powers of 2, powers can be found
far faster similar to finding 5^14 as 5^14 = 5^8 * 5^4 = ((5^2)^2)^2 * (5^2)^2 = x3 * x2 where
x1 = 5^2, x2 = x1^2, and x3 = x2^2, thus saving a lot of computations.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message