You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "John Mulcahy (JIRA)" <ji...@apache.org> on 2008/09/02 21:01:46 UTC
[jira] Created: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
QRDecomposition can easily be made to run about twice as fast
-------------------------------------------------------------
Key: MATH-223
URL: https://issues.apache.org/jira/browse/MATH-223
Project: Commons Math
Issue Type: Improvement
Affects Versions: 1.2
Environment: Any
Reporter: John Mulcahy
Priority: Minor
The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12635237#action_12635237 ]
Luc Maisonobe commented on MATH-223:
------------------------------------
the getQT() method has been added to the interface and implementation as proposed in the subversion repository (branch MATH_2_0) as of r699850).
thanks for the advice.
> QRDecomposition can easily be made to run about twice as fast
> -------------------------------------------------------------
>
> Key: MATH-223
> URL: https://issues.apache.org/jira/browse/MATH-223
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 1.2
> Environment: Any
> Reporter: John Mulcahy
> Assignee: Luc Maisonobe
> Priority: Minor
> Fix For: 2.0
>
> Attachments: QRDecompositionImpl.java
>
>
> The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-223?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe updated MATH-223:
-------------------------------
Fix Version/s: 2.0
this should be fixed for 2.0
> QRDecomposition can easily be made to run about twice as fast
> -------------------------------------------------------------
>
> Key: MATH-223
> URL: https://issues.apache.org/jira/browse/MATH-223
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 1.2
> Environment: Any
> Reporter: John Mulcahy
> Assignee: Luc Maisonobe
> Priority: Minor
> Fix For: 2.0
>
> Attachments: QRDecompositionImpl.java
>
>
> The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-223?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe resolved MATH-223.
--------------------------------
Resolution: Fixed
Fixed in subversion repository (branch MATH_2_0) as of r695251
The patch had to be slightly changed as it failed on non-square matrices.
A quick comparison with Jama shows that now for a QR-decomposition/solve pair, commons-math is between 40% and 50% faster than Jama.
Many thanks for the patch.
> QRDecomposition can easily be made to run about twice as fast
> -------------------------------------------------------------
>
> Key: MATH-223
> URL: https://issues.apache.org/jira/browse/MATH-223
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 1.2
> Environment: Any
> Reporter: John Mulcahy
> Assignee: Luc Maisonobe
> Priority: Minor
> Fix For: 2.0
>
> Attachments: QRDecompositionImpl.java
>
>
> The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
Posted by "John Mulcahy (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12627955#action_12627955 ]
John Mulcahy commented on MATH-223:
-----------------------------------
2.0 branch version looks good, can use the same transposed qr there including for the new solve routines to have the loops iterate over rows of the transposed matrix. Bear in mind that BLAS and LAPACK tend to assume column-major storage so for Java implementations it can be more efficient to change the algorithms so that 2D matrices are stored as their transposes and their indices are swapped within the algorithm. Plenty of scope for typos when doing that though :)
> QRDecomposition can easily be made to run about twice as fast
> -------------------------------------------------------------
>
> Key: MATH-223
> URL: https://issues.apache.org/jira/browse/MATH-223
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 1.2
> Environment: Any
> Reporter: John Mulcahy
> Priority: Minor
> Attachments: QRDecompositionImpl.java
>
>
> The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
Posted by "John Mulcahy (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-223?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
John Mulcahy updated MATH-223:
------------------------------
Attachment: QRDecompositionImpl.java
The attached file uses transposed qr and Q matrices. I haven't tested this (sorry!) as my own code doesn't use the Commons matrix classes, but exactly the same code using double[][] runs in just under half the time of the original when decomposing a 500x500 matrix.
> QRDecomposition can easily be made to run about twice as fast
> -------------------------------------------------------------
>
> Key: MATH-223
> URL: https://issues.apache.org/jira/browse/MATH-223
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 1.2
> Environment: Any
> Reporter: John Mulcahy
> Priority: Minor
> Attachments: QRDecompositionImpl.java
>
>
> The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
Posted by "John Mulcahy (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12632667#action_12632667 ]
John Mulcahy commented on MATH-223:
-----------------------------------
Looks good, thanks. One wrinkle which could still be added is for the calculation of the Q matrix. When that is explicitly required it is faster to calculate Q transpose and then transpose the result than to calculate Q directly. As an added benefit, people who want the Q matrix will often actually need Q transpose rather than Q itself so it is worth storing the transposed Q matrix and providing a method to obtain that directly.
> QRDecomposition can easily be made to run about twice as fast
> -------------------------------------------------------------
>
> Key: MATH-223
> URL: https://issues.apache.org/jira/browse/MATH-223
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 1.2
> Environment: Any
> Reporter: John Mulcahy
> Assignee: Luc Maisonobe
> Priority: Minor
> Fix For: 2.0
>
> Attachments: QRDecompositionImpl.java
>
>
> The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-223) QRDecomposition can easily be made to
run about twice as fast
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12627935#action_12627935 ]
Luc Maisonobe commented on MATH-223:
------------------------------------
Thanks.
Could you please have a look at the new implementation on the subversion repository, in 2.0 branch ?
Decomposition algorithms are currently being refactored a lot. One important modification is to had directly solve method in the decomposition class, thus removing the need for most user classes to call the getQ()/getR() or getU()/getL() methods.
I am currently working on the Singular Value Decomposition implementation (most probably using the wonderful MRRR algorithm). Once this will be done, I intend to make a performance improvement pass on all decomposition algorithms, in particular looking at cache-efficient implementations. Some ideas may be extracted from http://eprints.ma.man.ac.uk/210/01/covered/MIMS_ep2006_56.pdf (this is for bi-diagonalisation and this is using BLAS, but you get the idea).
> QRDecomposition can easily be made to run about twice as fast
> -------------------------------------------------------------
>
> Key: MATH-223
> URL: https://issues.apache.org/jira/browse/MATH-223
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 1.2
> Environment: Any
> Reporter: John Mulcahy
> Priority: Minor
> Attachments: QRDecompositionImpl.java
>
>
> The QRDecomposition will run much faster (about twice as fast) if the qr and Q matrices are calculated as their transposes and the transposition is sorted out in the getQ() method. Using the transposes allows the loops to iterate over rows of the transposed matrices rather than columns. It might also be useful to cache the Q matrix locally when it is generated in case there are any subsequent calls to getQ() as this is the most expensive part of the decomposition.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.