[#MATH-248] Multiplying sparse matrices is slow

Commons Math

Multiplying sparse matrices is slow

Created: 22/Feb/09 07:53 PM Updated: 23/Apr/09 02:26 AM

Return to search

Component/s:

None

Affects Version/s:

None

Fix Version/s:

2.0

Time Tracking:

Not Specified

Resolution Date:

05/Apr/09 04:54 PM

Description

« Hide

The multiplication of sparse real matrices is very slow compared to real matrices: Ten times as slow for size 200, four times as slow for size 400. The time is independent of the number of nonzero entries, because the general algorithm inherited from AbstractRealMatrix is used. I suggest using a specialized multiplication algorithm for matrices that are "sparse enough", walking only over the nonzero entries in one of the matrices.

All

Comments

Work Log

Change History

Subversion Commits

Sort Order:

[ Permlink | « Hide ]

Christian Semrau added a comment - 22/Feb/09 07:53 PM

According to my little tests, walking in optimized order and adding the pairwise products to the result matrix is much faster for very sparse matrices, but for a full matrix (every entry set to 1), it is about 50% slower than the current implementation. So the implementation might switch between the two algorithms. Also one might wish to walk the other matrix if it is more sparse than this.

[ Permlink | « Hide ]

Luc Maisonobe added a comment - 22/Feb/09 08:36 PM

You are right. It is probably even worse when compared to DenseRealMatrix which should be more cache-friendly than RealMatrixImpl.

It is also possible to walk through non-zero elements of both matrices.

Could you provide a patch for this ?

Luc Maisonobe made changes - 29/Mar/09 05:17 PM

Field	Original Value	New Value
Fix Version/s		2.0 [ 12312686 ]
Assignee		Luc Maisonobe [ luc ]

Repository	Revision	Date	User	Message
ASF	#762117	Sun Apr 05 16:53:35 UTC 2009	luc	Greatly improved multiplication speed for sparse matrices Jira: ~~MATH-248~~
				Files Changed
				MODIFY /commons/proper/math/trunk/src/site/xdoc/changes.xml MODIFY /commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SparseRealMatrixTest.java MODIFY /commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SparseRealMatrix.java

[ Permlink | « Hide ]

Luc Maisonobe added a comment - 05/Apr/09 04:54 PM

fixed in subversion repository as of r762117
thanks for the report

Luc Maisonobe made changes - 05/Apr/09 04:54 PM

Resolution		Fixed [ 1 ]
Status	Open [ 1 ]	Resolved [ 5 ]

Henri Yandell made changes - 23/Apr/09 02:26 AM

Status

Resolved [ 5 ]

Closed [ 6 ]