Previous | Next --- Slide 54 of 65
Back to Lecture Thumbnails

Why is it that a "sparse" system of linear equations would cause a computational bottleneck? Wouldn't a "dense" system (ie. many variables appearing in a large number of equations) also be an issue? In other words, what about the sparseness causes the computational bottleneck?


Correct me if I'm wrong, but I think the slide doesn't mean to imply that only sparse systems are hard to solve, but rather they are the most common when trying to model graphics. So it's not really the sparseness that causes the bottleneck, but the thing that causes the bottleneck just so happens to usually be sparse. Although I'm not sure about the computational difference between sparse and dense systems, so I might be interpreting the slide incorrectly.


@vik Yeah, that's the right idea. Big dense systems are definitely hard to solve, but even very large sparse systems also take a considerable fraction of the time in many modern graphics algorithms. For instance, in a basic fluid solver it's perhaps the most expensive part (though in general things like tracking the liquid surface may also cost a fair bit).