Closed mzy2240 closed 7 months ago
Hey @mzy2240 thanks for the thumbs up!
KLU solver does support a user-defined ordering, but this support is done at the C-language level. Do you have an example of a user-specified ordering? I could look at it and check how to pass the ordering function from Python to C.
Here you have the documentation for KLU
Thanks for the prompt reply!
Here is one example using cholmod with user defined ordering:
from kvxopt import matrix, spmatrix, cholmod, umfpack
from kvxopt.cholmod import options # klu module cannot import options
A = spmatrix([10, 3, 5, -2, 5, 2], [0, 2, 1, 3, 2, 3], [0, 0, 1, 1, 2, 3])
def test_default(A):
B = matrix(range(8), (4,2), 'd')
cholmod.linsolve(A,B)
%timeit test_default(A) # 16.1us per loop
options['nmethods'] = 1 # use user ordering ONLY
ordering = matrix(range(4))
def test_user_ordering(A):
B = matrix(range(8), (4,2), 'd')
cholmod.linsolve(A, B, p=ordering)
%timeit test_user_ordering(A) # 13.8 us per loop
Also thank you for the KLU document! Does that mean all the KLU functions have been wrapped and available to use with KVXOPT?
Also if possible and no huge work needed, could you please consider adding user ordering to UMFPACK function as well? I assume the procedure might be the same as KLU.
For KLU seems we may need to provide the ordering for each diagonal block, as the following piece of code is performed for each of them:
Do you thing you will get a faster KLU by providing the ordering of each diagonal block?
Regarding you KLU functions, I've currently implemented:
If I understand correctly (see attached), KLU also utilizes AMD for ordering during symbolic factorization. My idea is to use a custom ordering instead of AMD. Do you think it is possible? If not, the natural ordering is also fine, I just need to do a pre-permuation. Do you know any efficient implementation to do this permuatition? Directly permutating spmatrix seems to be slow.
Besides, could you also please expose the symbfact method to this python library? symbfact is very useful and efficient in terms of obtaining factorization tree and computing the number of fills.
Any updates on this?
Hi, have you tested the function klu.get_numeric?
That function interfaces to klu_extract.
Yes I carefully went through all the methods you have for KLU functions. I think the major problem is, as end python users, we don't have the access to klu_common object and this object appears in every klu function as the last parameter. If klu_common is accessible and editable, then natural ordering and user-defined ordering could be activated for any klu functions.
Indeed klu_common object is the best way to manipulate KLU internals, but some of their attributes are C (low level) functions/pointers (user_order). Which are not easy to interface to Python.
Yeah that makes sense. Another option is to provide a natural ordering option (set ordering=2
and P=Q=NULL
), so that users could perform an outer permutation in advance if they need to have a custom ordering. What do you think?
The difference with KLU versus other linear solvers such as UMFPACK is that it considers diagonal blocks, and each has a custom order. If you have a clear idea of how your block order needs to be, the interface to the user_order pointer makes sense; otherwise, permuting the matrix before entering KLU will not help. Klu will create blocks and remove any previous permutation, which is exactly the major contribution of KLU (create blocks).
Thank you for the notice. If you pay more attention to the document and the source code about how the natural ordering works in KLU, using ordering =2 with P and Q set to NULL will use exactly the order that matrix has (of course with the tradeoff of losing the performance gain from block operation).
Great package! Just wonder whether the KLU solver supports custom ordering instead of the default AMD? I noticed cholmod supports this feature *1, but awkwardly I cannot find any documents about this for KLU.
BTW, I tried to search KLU as key words in this repo but cannot find any code related. Where should I find the relevant doc and source code? Sorry for this dumb question and thank you in advance!
Again, great package! KLU is FAST!