1
$\begingroup$

I have a question regarding the computational complexity of the ILU preconditioner in Python. I am trying to implement an ILU(0) preconditioner using the following code:

ILUfact = sla.spilu(resultant_matrix_csc, drop_tol=0, fill_factor=1)

In this code, resultant_matrix_csc is a sparse matrix. When I run this code on a matrix with N non-zero elements and then on a matrix with 4N non-zero elements, I expect the execution time to increase by a factor of 4. However, in practice, the time difference varies between 8 and 16 times.

I have also checked the fill-ins in the resulting L and U matrices, and since I am using ILU(0), the total number of non-zero elements in the factorized matrices is approximately the same as in the original matrix. Given this, I would expect the complexity of the ILU(0) algorithm to be O(nnz), where nnz represents the number of non-zero elements. However, my observations indicate a different complexity.

What could be the reason for this discrepancy? I want to understand the reason of this difference. Additionally, my goal is to achieve linear complexity. How can I optimize my use of the ILU preconditioner for the most efficient performance? Do you have any suggestions for other tools that I can use in Python?

Thank you,

Improve this question
$\endgroup$
1
  • $\begingroup$ You have to expect that the cost of computing an LU decomposition cannot be less than what it costs to compute the product of $L$ times $U$. That cost is likely proportional to $nnz^2$. $\endgroup$ Commented Oct 23, 2024 at 22:57

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.