Gaussian Elimination

A method of solving Matrix equations of arbitrary size (CramersRule? is quicker by hand for up to 3*3 Matrices but from size 4 and up this is needed). Can be done by pencil and paper but computers are usually used. The goal is to apply elementary row operations to reduce the lower diagonal of the matrix to zero which allows the answer to be derived from the remaining values. See also http://mathworld.wolfram.com/GaussianElimination.html

It's trivial and mechanical unless your problem is ill-conditioned, and then it gets really, really hard.

My understanding was that it wasn't just a sharp line between the easy cases and the really hard ill-conditioned cases, but that actually there was a very large area in between that was better addressed by other algorithms, which are not as fast as GaussianElimination, but which are more reliable in the face of instabilities. If my memory is correct, what about those other algorithms?

It's true that ill-conditionedness is not binary, it's also true that inappropriate algorithms (or choices within algorithms) can make a problem ill-conditioned. I believe that dealing with ill-conditioned problems is a case of choosing carefully which rows to combine and which factors to multiply by, rather than using an entirely different algorithm. In other words, it's the same algorithm, but the choices made within it are constrained.

Mmm, well, partially, but there was more to my vague memory than just a question of pivots, so I just did a quick search, and I see claims that e.g. conjugate gradient iteration is better for random matrices. I think it's a complex subject, algorithmically.

CategoryMath CategoryAlgorithm