UMFPack::setSubMatrix can degenerate to O(n^2) complexity
The non-ignored rows are passed to ISTL as MatrixRowSubset. When setting up the UMFPack matrix the ColCompMatrixInitializer
calls addRowNnz
for each row in the sub-matrix. To determine the nnz entries in the row addRowNnz
itself loops simultaneously over all row entries and the set of sub-matrix indices. This can easily degenerate to O(n^2) complexity for sparse matrices. One example where O(n^2) complexity shows up is a diagonal matrix where the sub-matrix index set contains all rows.
I guess the implementation could easily be fixed: The subMatrixIndex
vector created afterwards could be used as a look-up vector to check if the row entries are in the sub-matrix in O(1). Unfortunately I don't have time to fix this now.