You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org> on 2010/11/08 23:26:25 UTC
[jira] Created: (MATH-435) Efficient matrix power
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.
[jira] [Resolved] (MATH-435) Efficient matrix power
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mikkel Meyer Andersen resolved MATH-435.
----------------------------------------
Resolution: Fixed
Fixed for FieldMatrix<T> in revision 1083713.
> 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
> Fix For: 3.0
>
> Attachments: MATH435-patch1
>
> Original Estimate: 4m
> Remaining Estimate: 4m
>
> 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.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Issue Comment Edited: (MATH-435) Efficient matrix power
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12929987#action_12929987 ]
Mikkel Meyer Andersen edited comment on MATH-435 at 11/9/10 1:55 AM:
---------------------------------------------------------------------
Of course numerical instability still occurs for large powers. One possibility is to extract scalars of the type 10eX for integer X, i.e. both positive and negative, and then return X together with the scaled result. This requires a bit more bookkeeping, but might be a good idea. Of course, if the matrix is to be used directly, this doesn't change much, but for further processing this actually might save the day.
was (Author: mikl):
Of course numerical instability still occurs for large powers. One possibility is to extract scalars of the type 10eX for integer X, i.e. both positive and negative, and then X together with the scaled result. This requires a bit more bookkeeping, but might be a good idea. Of course, if the matrix is to be used directly, this doesn't change much, but for further processing this actually might save the day.
> 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
> Attachments: MATH435-patch1
>
> Original Estimate: 0.07h
> Remaining Estimate: 0.07h
>
> 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.
[jira] Commented: (MATH-435) Efficient matrix power
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12929987#action_12929987 ]
Mikkel Meyer Andersen commented on MATH-435:
--------------------------------------------
Of course numerical instability still occurs for large powers. One possibility is to extract scalars of the type 10eX for integer X, i.e. both positive and negative, and then X together with the scaled result. This requires a bit more bookkeeping, but might be a good idea. Of course, if the matrix is to be used directly, this doesn't change much, but for further processing this actually might save the day.
> 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
> Attachments: MATH435-patch1
>
> Original Estimate: 0.07h
> Remaining Estimate: 0.07h
>
> 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.
[jira] Commented: (MATH-435) Efficient matrix power
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13008938#comment-13008938 ]
Phil Steitz commented on MATH-435:
----------------------------------
+1 to commit this. Maybe add warning to javadoc about stability for higher powers.
> 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
> Fix For: 3.0
>
> Attachments: MATH435-patch1
>
> Original Estimate: 4m
> Remaining Estimate: 4m
>
> 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.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Reopened] (MATH-435) Efficient matrix power
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mikkel Meyer Andersen reopened MATH-435:
----------------------------------------
FieldMatrix also has to have the (duplicate) power functionality.
> 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
> Fix For: 3.0
>
> Attachments: MATH435-patch1
>
> Original Estimate: 4m
> Remaining Estimate: 4m
>
> 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.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (MATH-435) Efficient matrix power
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-435:
-----------------------------
Fix Version/s: 3.0
> 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
> Fix For: 3.0
>
> Attachments: MATH435-patch1
>
> Original Estimate: 0.07h
> Remaining Estimate: 0.07h
>
> 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.
[jira] [Resolved] (MATH-435) Efficient matrix power
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mikkel Meyer Andersen resolved MATH-435.
----------------------------------------
Resolution: Fixed
Fixed in revision 1083698.
> 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
> Fix For: 3.0
>
> Attachments: MATH435-patch1
>
> Original Estimate: 4m
> Remaining Estimate: 4m
>
> 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.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (MATH-435) Efficient matrix power
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mikkel Meyer Andersen updated MATH-435:
---------------------------------------
Attachment: MATH435-patch1
Patch proposal
> 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
> Attachments: MATH435-patch1
>
> Original Estimate: 0.07h
> Remaining Estimate: 0.07h
>
> 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.
[jira] [Commented] (MATH-435) Efficient matrix power
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-435?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13009058#comment-13009058 ]
Mikkel Meyer Andersen commented on MATH-435:
--------------------------------------------
Two post-fixes: 1083704 for removing @Override for consistency and 1083706 for missing @Test annotation on test case.
> 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
> Fix For: 3.0
>
> Attachments: MATH435-patch1
>
> Original Estimate: 4m
> Remaining Estimate: 4m
>
> 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.
For more information on JIRA, see: http://www.atlassian.com/software/jira