[petsc-users] a cost question for sparse factorization

[Jed Brown]

On Sat, Apr 28, 2012 at 04:25, Umut Tabak <u.tabak at tudelft.nl> wrote:

> Dear all,
>
> My question is not directly related to PETSc however it fits the audience
> on this list properly. Where can I find the computational cost analysis on
>
> + sparse cholesky factorization,
> + sparse LDL^T factorization,
>
> in relation to the bandwidth of my sparse matrices. All the references I
> have present these costs for dense matrices. Where shall I look to get an
> overview on these costs for sparse/band matrices?
>

All you will get are asymptotics, not sharp operation counts. For 2D, the
bounds are O(n^{1.5} flops and O(n log n) space; for 3D they are O(n^2)
flops and O(n^{4/3}) space. This is covered in Alan George's book,
http://www.cse.illinois.edu/courses/cs598mh/george_liu.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20120428/a1c026e8/attachment.htm>