The Living Thing / Notebooks : Large (output) linear (ish) solvers

Matrix mangling for fun and… actually because its not fun and someone else’s solvers are better than yours; they probably have a PhD in it, right?

Solving large systems of equations is not conceptually distinct from optimisation. But, er, there are differences in emphasis between

Here I concentrate on the latter.

Clearly artificial neural network require solving what sounds like kind of problem, but they are very very nonlinear, hence kind of a different specialisation. There is some overlap.

Examples applications for solvers can include (especially elliptic) PDEs, inverse/tomography-style image reconstruction, classical optimisation, boring old quadrature, linear transform methods, integral equations, and general sparse-ish problems, various general matrix factorisations

In many of these domains, there might be structure to exploit, and solvers which can exploit this in some smart way. For example, the description of a discretised PDE usually reduces to a banded matrix and hence a sparse problem.

There are many iterative methods for this kind of system.

Geometric multigrid, algebraic multigrid. Stochastic methods….

See Yousef Saad’s textbooks on algebraic multigrid methods. (free online)


Brezina, M., Cleary, A., Falgout, R., Henson, V., Jones, J., Manteuffel, T., … Ruge, J. (2001) Algebraic Multigrid Based on Element Interpolation (AMGe). SIAM Journal on Scientific Computing, 22(5), 1570–1592. DOI.
Briggs, W. L., Henson, V. E., & McCormick, S. F.(2000) A Multigrid Tutorial: Second Edition. . SIAM
Guyer, J. E., Wheeler, D., & Warren, J. A.(2009) FiPy: Partial Differential Equations with Python. Computing in Science & Engineering, 11(3), 6–15. DOI.
Stüben, K. (2001) A review of algebraic multigrid. Journal of Computational and Applied Mathematics, 128(1–2), 281–309. DOI.
Trottenberg, U., Oosterlee, C. W., & Schuller, A. (2000) Multigrid. . Academic Press
Vanek, P., Mandel, J., & Brezina, M. (1996) Algebraic Multigrid By Smoothed Aggregation For Second And Fourth Order Elliptic Problems. COMPUTING, 56, 179–196.