What would some of the difference be between a sparse vs a dense solver?

Is it something like the kind of factorization used to solve the linear system, because I can see sparse matrices (especially like the one on the slide) being really easy to factorize by using a LU decomposition vs a dense matrix or is it something else?

kmcrane

@kapalani: See the slide immediately following this one. The difference is in the data structures: dense means you store every entry, sparse means you store only nonzeros. Of course, depending on the data structure you pick, the algorithms will have to look different as well.

For sparse factorization in particular, the very rough idea is to apply the same factorization algorithms as for dense matrices, but change the ordering of rows and columns so that (hopefully) the factorizations remain reasonably sparse. In 2D, for operators like Laplace, there are good heuristics that tend to keep things nice and sparse. In general, it's an interesting and challenging problem. Fortunately, you usually do not have to worry about these issues yourself: modern linear solvers hide a lot of complexity under the hood.

What would some of the difference be between a sparse vs a dense solver?

Is it something like the kind of factorization used to solve the linear system, because I can see sparse matrices (especially like the one on the slide) being really easy to factorize by using a LU decomposition vs a dense matrix or is it something else?

@kapalani: See the slide immediately following this one. The difference is in the data structures: dense means you store every entry, sparse means you store only nonzeros. Of course, depending on the data structure you pick, the algorithms will have to look different as well.

For sparse factorization in particular, the very rough idea is to apply the same factorization algorithms as for dense matrices, but change the ordering of rows and columns so that (hopefully) the factorizations remain reasonably sparse. In 2D, for operators like Laplace, there are good heuristics that tend to keep things nice and sparse. In general, it's an interesting and challenging problem. Fortunately, you usually do not have to worry about these issues yourself: modern linear solvers hide a lot of complexity under the hood.