Hi list,
I want to ask why LU decomposition has been used for matrix solving in RST library when matrix being solved is symmetric. I am planning to solve it using Cholesky decomposition.
I want to confirm with grass developers that there is no issue if I solve it using Cholesky decomposition. My goal is not to change current serial implementation, I am implementing (started, at least) v.surf.rst on GPU and planning to use Cholesky instead of LU as it is expected to show better performance over LU.
Please someone confirm that it is okay to solve matrix using Cholesky decomposition.
Abhishek Shukla
Center for Security, Theory And Algorithm Research (CSTAR)
International Institute of Information Technology
Hyderabad
India
http://www.iiit.ac.in/
On Mon, May 3, 2010 at 1:45 AM, Soeren Gebbert <soerengebbert@googlemail.com> wrote:
Hello,
LU is used to solve the linear equation system, because the matrix is
not positive definite. There is a zero at the diagonal. You can try to
sort the rows and cols, but i’m not sure if the matrix will get
positive definite. Maybe an LDL decomposition can be used instead of
LU.
I have tried to solve the linear equation system with a parallele
BiCGStab algorithm, but most of the time the linear equation system is
of very bad condition, so the BiCGStab solver fails. An LU algorithm
with pivoting is needed.
Hence, reordering rows and cols to avoid a zero at the diagonal and
parallel LDL decomposition may be the best choice.
I believe you meant LDU decomposition here.
The RST Matrix looks most of the time like this:
0.0 1.0 1.0 1.0
1.0 -0.1 3.0 2.5
1.0 3.0 -0.1 2.2
1.0 2.5 2.2 -0.1
I do not understand the matrix assembling algorithm, nor the spline
interpolation algorithm, so i don’t know how the zero at the diagonal
can be prevented on algorithm side.
There are many people out there in grass-dev list who understand these. I request them to please reply.
Best regards
Soeren
2010/5/2 Abhishek Shukla <abhishekiiith@gmail.com>:
Hi list,
I want to ask why LU decomposition has been used for matrix solving in RST
library when matrix being solved is symmetric. I am planning to solve it
using Cholesky decomposition.
I want to confirm with grass developers that there is no issue if I solve it
using Cholesky decomposition. My goal is not to change current serial
implementation, I am implementing (started, at least) v.surf.rst on GPU and
planning to use Cholesky instead of LU as it is expected to show better
performance over LU.
Please someone confirm that it is okay to solve matrix using Cholesky
decomposition.
Abhishek Shukla
Center for Security, Theory And Algorithm Research (CSTAR)
International Institute of Information Technology
Hyderabad
India
http://www.iiit.ac.in/
grass-dev mailing list
grass-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-dev
Helo,
2010/5/3 Abhishek Shukla <abhishekiiith@gmail.com>:
On Mon, May 3, 2010 at 1:45 AM, Soeren Gebbert
<soerengebbert@googlemail.com> wrote:
Hello,
LU is used to solve the linear equation system, because the matrix is
not positive definite. There is a zero at the diagonal. You can try to
sort the rows and cols, but i'm not sure if the matrix will get
positive definite. Maybe an LDL decomposition can be used instead of
LU.
I have tried to solve the linear equation system with a parallele
BiCGStab algorithm, but most of the time the linear equation system is
of very bad condition, so the BiCGStab solver fails. An LU algorithm
with pivoting is needed.
Hence, reordering rows and cols to avoid a zero at the diagonal and
parallel LDL decomposition may be the best choice.
I believe you meant LDU decomposition here.
Nope, i mean LDL. Ok, the mathematical correct description is LDL^T.
http://www.cise.ufl.edu/research/sparse/ldl/
Best regards
Soeren