HACKER Q&A
📣 helltone

Incremental Precision Solver


I have a system of equations or constraints over multiple variables. Most numerical solvers seem to compute some floating point solution at a fixed precision (float or double). I wonder if there are any approaches where the precision can be chosen, either upfront (user defined) or afterwards, that is, first a solution is given at some precision and then the user can ask for it to be improved (more iterations of whatever numerical solver), until user is happy with the precision. I assume perhaps interval arithmetic would be appropriate for this. Any pointers?

  👤 stncls Accepted Answer ✓
It depends on the types of constraints you have, the precision you want, and the sparsity of the system.

For example, for linear equality constraints, one general approach is iterative refinement [1]. If you are using floats/doubles and have dense systems, Lapack has implementations at some precision levels [2] (although not necessarily those you want).

For arbitrary precision, maybe look at MPFR matrices in flint [3].

If you have sparse systems using doubles there are papers on iterative refinement in suitesparse, but I don't know if the implementations are public.

If you have sparse inequality constraints, you can try SoPlex [4].

[1] https://en.wikipedia.org/wiki/Iterative_refinement

[2] https://netlib.org/lapack/explore-html/d7/d3b/group__double_...

[3] http://flintlib.org/sphinx/mpfr_mat.html

[4] https://soplex.zib.de/doc-1.7.0/html/IR.html