Fastest method in LAPACK for solving positive definite symme

Open discussion regarding features, bugs, issues, vendors, etc.

Fastest method in LAPACK for solving positive definite symme

Postby Eigen_solver » Wed Oct 21, 2015 8:12 am

dear All,

I have positive definite symmetrix matrix, which is obtained as global stiffness matrix from classical solid mechanic principles K*X = F , I used gauss elimination and LU decomposition method to solve the linear algebraic problem, but the solution time is too much for e.g. for 1K matrices. Quick search reveals that this is known issue for gauss and LU decomposition, for faster solutions its' been adviced to incorporate different solution scehems, but that also requires complete modification of global stiffness matrix.

My question is : What is the fastest method in Lapack which will not require the modification of stiffness matrix?

Regards,
Eigen_solver
 
Posts: 19
Joined: Fri Jun 01, 2012 6:08 am

Re: Fastest method in LAPACK for solving positive definite s

Postby Julien Langou » Wed Oct 21, 2015 7:02 pm

Stiffness matrices are symmetric positive definite. They are also often banded, and often sparse as well. If you want an efficient solver, you need to take all this into account. If you stick to LAPACK, you can use xPOSV for solving the system of equations (instead of xGESV). You will be using a Cholesky factorization instead of an LU factorization with partial pivoting. This does not require any change in your data format. The gain will be minimal (a factor of 2 or so). You probably want to other changes to get more speedup. The next thing to do would be to take into account the banded structure of your matrix. You want to use xPBSV. This requires a change in the data structure. You will use less memory, and this should be much faster. That's about it for what LAPACK can do for you. The next step (which is advisable) is to use a sparse direct Cholesky solver. Please look on the internet and you should find a few. Another options is to look at sparse iterative methods for symmetric positive definite matrices (like the Conjugate Gradient method). So to repeat: (1) LAPACK xPOTRF, (no change, minimal gain) (2) LAPACK xPBTRF (change in data structure, some significant gain, hopefully, depends on 1D, 2D or 3D), (3) sparse direct Cholesky solver, (4) sparse iterative Cholesky methods for symmetric positive definite matrices. Best wishes, Julien.
Julien Langou
 
Posts: 835
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

Re: Fastest method in LAPACK for solving positive definite s

Postby Eigen_solver » Fri Oct 23, 2015 4:17 am

Hi thanks in advance,

It seems that for efficient and robust solutions element by element and effective storage mehanisms need to be employed. In a long run inevitably I'll use those with proper storage scehemes, I'll start with easiest to hardest iterating gradually, for the starting point now I plan skyline storage and Cholesky factorization I think that I'll gain much since I introduce a storage mechanism. But seems that skyline storage pattern may differ slightly, some stores non-zero and some stores elements including in-between zeros, so how am I supposed to integrate those with Lapack Cholesky functions?

I googled for:" skyline storage with Cholesky factorization" but that dind't retrieved anything usefuly, any snippets or entry point will be appreciated!

Regards,
Eigen_solver
 
Posts: 19
Joined: Fri Jun 01, 2012 6:08 am


Return to User Discussion

Who is online

Users browsing this forum: No registered users and 3 guests

cron