This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen
Bug 1456 - LLT::rankUpdate() is slow for RowMajor matrices
Summary: LLT::rankUpdate() is slow for RowMajor matrices
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Cholesky (show other bugs)
Version: 3.3 (current stable)
Hardware: All All
: Normal Performance Problem
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2017-08-04 10:22 UTC by Björn Barz
Modified: 2019-12-04 17:08 UTC (History)
2 users (show)



Attachments
Performance benchmark for LL::rankUpdate() (989 bytes, text/x-c++src)
2017-08-04 10:22 UTC, Björn Barz
no flags Details

Description Björn Barz 2017-08-04 10:22:48 UTC
Created attachment 794 [details]
Performance benchmark for LL::rankUpdate()

LLT::rankUpdate() takes considerably longer on RowMajor matrices than on ColMajor ones.

The attached code can be used to measure the execution time of 100 random updates to the Cholesky decomposition of a random 5000-by-5000 matrix. Compile it as follows:

    g++ -Wall -O3 --std=c++11 -o rank_update_col eigen_rank_update.cc
    g++ -Wall -O3 --std=c++11 -DROWMAJOR -o rank_update_row eigen_rank_update.cc

And then run:

    ./rank_update_col; ./rank_update_row

The ColMajor version takes 8.2 seconds on my system, while the RowMajor variant needs 22.9 seconds.
Comment 1 Björn Barz 2017-08-04 10:46:22 UTC
The situation is reversed when computing the upper triangular decomposition instead of the (default) lower triangular. So, this is probably not really a bug, but just natural. However, maybe it should be documented that upper triangular decompositions provide better performance for row-major storage format.
Comment 2 Gael Guennebaud 2017-08-22 10:48:26 UTC
Right, this is also true for the full factorization, though the impact is lower. Added doc:

https://bitbucket.org/eigen/eigen/commits/3efa9819ef30/
https://bitbucket.org/eigen/eigen/commits/c8c154ebf130/ (3.3)
Comment 3 Nobody 2019-12-04 17:08:13 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/1456.

Note You need to log in before you can comment on or make changes to this bug.