[Insight-users] solving large linear equations

[Arnaud Gelas]

Habib,

Thanks for sending your code. I have just tested it...
You're right the LU decomposition is really slow. I have checked the 
condition number, it is large 38322.4 (given by vnl_sparse_lu), but 
should be ok? (If anyone could comment this number, it would be great!?)

I have looked at the structure of your matrix, and I really think with 
such kind of matrix the LU decomposition should be really fast (due to 
the sparsity and the well defined block structure in the matrix). I am 
not sure about vnl strategy for the LU decomposition, and I would be 
interested if any vnl guy could answer these questions:
 * what ordering strategy is used? Is the graph of the matrix used in 
the factorization?
 * what kind of technique is used? Left-looking? Frontal? Multifrontal?

Since you are looking for performance, and I don't know if you have any 
license constraint, I would recommend you to have a look at:
 * UMFPack: http://www.cise.ufl.edu/research/sparse/umfpack/
 * SuperLU: http://crd.lbl.gov/~xiaoye/SuperLU/
 * TAUCS: http://code.google.com/p/taucs/

There are other libraries out there which could do the job for you, and 
I guess some other guys in the list could recommend bunch of others... 
(Those one are quite famous for their performances...)

Have a nice day,
Arnaud

Habib Baluwala wrote:
> Arnaud , 
>           It takes around 10 min to solve the linear system of equations. I
> also tried the vnl_sparse_matrix_linear_system but that too takes a long
> time for solving these equations. 
>
>
>
>
> Arnaud Gelas wrote:
>   
>> Habib,
>>
>> Right, your matrix is not that large and is really sparse...
>> I am curious to know how long it takes to solve your system?
>>
>> I am not so sure about the efficiency of vnl direct solver (LU 
>> solver)... (Until recently, sparse iterative solver were really 
>> efficient in comparison to direct ones, and this is still a very active 
>> field of research!)
>> If you need to solve several times linear systems which involve the same 
>> matrix, I would recommend to use a direct solver like LU, LLT, LDLT; 
>> else an iterative solution like vnl_sparse_matrix_linear_system.
>>
>>
>> Arnaud
>>
>>
>>
>> Habib Baluwala wrote:
>>     
>>> Hi Arnaud, 
>>>                The size of the matrix is around 40,000 rows and columns
>>> but
>>> the density is around 5 percent which is very small. I am using the
>>> vnl_sparse_matrix for reading the sparse matrix and then using the
>>> vnl_sparse_lu and for solving the equations. I thought that the blas and
>>> lapack libraries are linked with the linear solver but that does not seem
>>> to
>>> be the case or I am currently not using any pointers for the sparse
>>> matrix.
>>> Can this be a reason for the failure????? I look forward to yor reply 
>>>
>>>
>>>
>>>
>>>
>>> Arnaud Gelas wrote:
>>>   
>>>       
>>>> Hi habbib,
>>>>
>>>> How large is your matrix?
>>>> How sparse is your matrix? Do you know the number of non null elements 
>>>> in your matrix? Or can you tell me the number of non null elements per 
>>>> row (in average)?
>>>>
>>>> Solving sparse linear system highly depends on the sparsity of your
>>>> matrix.
>>>> When you say I am "using VNL sparse system solver", what do you mean? 
>>>> which class are you using?
>>>>
>>>> Note that it is not because you use BLAS and LAPACK that the code will 
>>>> be fast, it depends how they are used in in the library. For example 
>>>> mumps, taucs are also based on blas and lapack and performances are 
>>>> really different...
>>>>
>>>> Arnaud
>>>>
>>>> Habib Baluwala wrote:
>>>>     
>>>>         
>>>>> Hi everyone , 
>>>>>                  I am currently using a large sparse system of linear
>>>>> equation which is non-symmetric. I tried using VNL sparse system
>>>>> solvers
>>>>> but
>>>>> they are very slow , I can't still understand why they are slow because
>>>>> they
>>>>> are supposed to utilise the BLAS and Lapack libraries to speed up. Can
>>>>> anyone tell me how can I speed up the procedure???? I also tried the
>>>>> release
>>>>> instead of debug. It was able to reduce the time taken but not to a
>>>>> significant effect. Would including the Utilities folder in the
>>>>> CMakeFile.txt help ???
>>>>>
>>>>> I look forward to your reply and sorry for any inconvenience. 
>>>>>
>>>>>
>>>>>
>>>>>   
>>>>>       
>>>>>           
>>>> _____________________________________
>>>> Powered by www.kitware.com
>>>>
>>>> Visit other Kitware open-source projects at
>>>> http://www.kitware.com/opensource/opensource.html
>>>>
>>>> Please keep messages on-topic and check the ITK FAQ at:
>>>> http://www.itk.org/Wiki/ITK_FAQ
>>>>
>>>> Follow this link to subscribe/unsubscribe:
>>>> http://www.itk.org/mailman/listinfo/insight-users
>>>>
>>>>
>>>>     
>>>>         
>>>   
>>>       
>> _____________________________________
>> Powered by www.kitware.com
>>
>> Visit other Kitware open-source projects at
>> http://www.kitware.com/opensource/opensource.html
>>
>> Please keep messages on-topic and check the ITK FAQ at:
>> http://www.itk.org/Wiki/ITK_FAQ
>>
>> Follow this link to subscribe/unsubscribe:
>> http://www.itk.org/mailman/listinfo/insight-users
>>
>>
>>     
>
>