Linear System Solver
At each iteration \(k\) SCS solves the following set of linear equations:
for a particular right-hand side \(z^k \in \mathbf{R}^{n+m}\). The presence of the diagonal scaling \(R \in \mathbf{R}^{(n+m) \times (n+m)}\) matrix is explained in Non-identity DR Scaling. The \(R_y\) term is negated to make the matrix quasi-definite; we can recover the solution to the original problem from this modified one. Note that the matrix does not change from iteration to iteration, which is a major advantage of this approach. Moreover, this system can be solved approximately so long as the errors satisfy a summability condition, which permits the use of approximate solvers that can scale to very large problems. SCS also solves the system once for the right-hand side \((c, -b)\) at the start of every solve and whenever \(R\) changes; how accurately SCS makes both kinds of solve is described in Iterative refinement.
Iterative refinement
Write \(K\) for the matrix above. How accurately SCS can solve a problem is limited by how accurately it solves systems with \(K\): its residuals cannot become much smaller than the error of those solves. Inexact solves are fine while the residuals are large (the algorithm tolerates errors that satisfy the summability condition above), but near the requested accuracy an inexact solve holds the iterates back. A factorization can lose accuracy on a badly scaled or ill-conditioned \(K\), and conjugate gradients stops at a tolerance. So SCS checks the solves it depends on, by computing their residuals, and when one is not accurate enough it refines it: it solves with \(K\) for the residual and adds the correction to the solution that residual belongs to. For the \((c, -b)\) solve and with the indirect solvers that is an extra solve; for the direct solvers’ per-iteration solves it takes the place of the plain solve (see below). Two solves are checked, each in its own way:
the solve for the right-hand side \((c, -b)\), made at the start of a solve and whenever \(R\) changes and used in every iteration until the next change, is solved to about machine precision every time it is made, with at most five refinement steps (see The solve for (c, -b));
each iteration’s solve is checked every 25 iterations against SCS’s own residuals, and made more accurate while its error would hold the iterates back (see Accuracy of each iteration’s solve).
There is nothing to set: both always run, with every linear solver (direct and indirect, on the CPU and the GPU) and in every interface, and no setting turns them off. They are deterministic: every decision depends only on the iterates and the residuals, never on timings or load, so they add no run-to-run variation of their own. Their costs are given in the two subsections below.
This is not the per-row refinement of the scaling \(R\) (see
Per-row refinement), which changes \(R\) itself, nor the refinement
of the small least-squares solve inside Acceleration, nor the
refinement cuDSS does inside its own solves in single precision (see
Sparse GPU direct method), nor the two refinement steps MKL Pardiso takes inside a
solve when its factorization had to perturb a pivot (iparm[7] = 0 with
iparm[9] = 13, see MKL Pardiso).
SCS’s linear solve takes a warm start, a tolerance and a number of refinement steps (see Implementing a new linear solver). The per-iteration refinement uses it for both kinds of solver and decides only when: with the direct solvers it passes the previous iteration’s solution as the warm start, and with the indirect solvers it asks for refinement steps. The solve for \((c, -b)\) passes its first solution as the warm start, a tolerance at about machine precision and at most five steps in all, with every solver (see below).
The solve for \((c, -b)\)
When and why. At the start of every solve, and whenever the scaling \(R\), and so \(K\), changes (see Dynamic scale updating), SCS solves \(K g = (c, -b)\). Every iteration until the next change uses that \(g\): it enters the quadratic that gives \(\tau\) (the root-plus function in Non-identity DR Scaling, where it is written \(r\)), and \(\tau g\) is subtracted from that iteration’s solve. An error in an iteration’s own solve affects one iteration; an error in \(g\) is repeated in every iteration rather than averaged out, and can limit the accuracy SCS reaches. So \(g\) is solved to about machine precision every time it is computed, rather than as accurately as SCS’s current residuals need, as each iteration’s solve is.
The tolerance. A plain solve (with conjugate gradients: from zero, to
the solvers’ best accuracy, CG_BEST_TOL) gives \(g_0\) and its
residual \(r = (c, -b) - K g_0\). SCS then refines \(g\) until a
step no longer halves the residual, which is where the linear solver can do
no better. The tolerance it passes to the solve,
(absolute values entry by entry; G_TOL_EPS in
include/glbopts.h), with \(\epsilon\) the machine epsilon of the
precision SCS is built in, is set just below what refinement reaches, so
that the steps end at that halving stop rather than at the tolerance.
Refined that far, the residual of \(g\) is 0.3 to 0.4 machine epsilons
of the size of its terms (the median with QDLDL and conjugate gradients, on
the CPU and the GPU, in double and single precision, on random SOCPs; at
most 1.7): the rounding errors of the terms of a row partly cancel. (The
rounding level of the per-iteration refinement below, four machine
epsilons of the terms, is a bound with room; this is the typical size.)
A tolerance the solver can meet would stop it earlier, since conjugate
gradients solves each step only to the tolerance and so lands just below
it, and in single precision that matters. An iteration that uses a computed
\(g\) is exact for the data \(K g\), that is for \(c - r_x\) and
\(b + r_y\) with \(r = (c, -b) - K g\), so the residual of \(g\)
is a floor under SCS’s residuals that no number of iterations removes. At
\(10^{-6}\), about eight single-precision epsilons, that floor can reach
SCS’s tolerance where the rows are dense: with a tolerance of
\(4 \epsilon\), single-precision conjugate gradients left \(g\) at
3.4 epsilons of its terms on random SOCPs with 100 variables and dense rows,
and 72 of 100 ran to max_iters or the time limit; refined to the
halving stop, none did, and single precision with conjugate gradients was
about three times faster over 500 random SOCPs. In double precision the
floor is about \(10^{-6}\) of SCS’s tolerance at \(10^{-9}\).
The size is computed row by row, from the entries each row actually multiplies, rather than as \(\|(c, -b)\|_\infty + \|K\|_\infty \|g_0\|_\infty\) (the normwise backward error), which pairs the largest row of \(K\) with the largest entry of \(g_0\) even where they do not meet: on badly scaled problems that was up to \(10^9\) times larger, and would have accepted residuals far above rounding. It is one number, the largest row’s, because the tolerance of the solve bounds the largest entry of the residual; so a row whose terms are much smaller than the largest row’s is held to the largest row’s rounding, not to its own.
The refinement. If \(g_0\) misses the tolerance, the solve is
repeated with \(g_0\) as its warm start, to the tolerance, with at most
five steps in all (G_REFINE_MAX_STEPS). For a direct solver the
first step is the correction form from \(g_0\); for conjugate gradients
it is a solve started from \(g_0\). Each further step computes the
residual with \(K\) and adds the solution of \(K d = r\) (by
conjugate gradients from zero to the tolerance, with them). A step is kept
only if it lowers the residual, the steps stop after one that does not at
least halve it, and SCS keeps \(g_0\) unless the result is better, so
\(g\) never has a larger residual than the first solve. Conjugate
gradients solves a reduced system and computes \(g_y\) from
\(g_x\), so on badly scaled data its own rounding can be far above that
of \(K\)’s residual: the solve started from \(g_0\) is limited by
that rounding, but each further step solves only for the correction, so it
is not.
If it fails. The solve should never fail. If the linear solver returns
an error, \(g\) is not finite, or the residual of the refined \(g\)
is more than half the size of its terms (G_FAIL_REL_RES: not even
the leading digit right; with working solvers it measured at most about
\(10^{-2}\) of the size, and that only where the solver could do no
better, such as conjugate gradients at its iteration limit), SCS stops with
status SCS_FAILED (see Exit flags) and prints what failed,
that this indicates a bug in SCS or its linear solver, and a request to open
an issue at https://github.com/cvxgrp/scs/issues with the problem data (the
write_data_filename setting saves it). If \(b\) or \(c\)
contains a NaN or infinite entry, SCS stops with SCS_FAILED and says
so instead.
Cost. One multiply by \(K\) each time \(g\) is solved for (the residual of \(g_0\)) and one pass over \(A\) and \(P\) for the size of the terms, paid even when the first solve is already accurate enough; when it is not, one solve and one multiply per step, and with a direct solver one multiply more (the correction form computes the residual of \(g_0\) again). The steps run until one no longer halves the residual, which usually takes one step more than stopping at a tolerance the solver can meet. With a direct solver each solve reuses the existing factorization, so this is cheap next to factorizing. With the indirect solvers each step costs the conjugate gradient iterations that reach the tolerance: on random SOCPs the refinement took about 14% of the first solves’ conjugate gradient iterations in double precision (over whole solves, up to 2% more conjugate gradient iterations and 1 to 1.5% more time than with a tolerance of \(4 \epsilon\)), and about 60% in single precision, where the more accurate \(g\) made whole solves about three times faster. Where conjugate gradients cannot reach the tolerance within its iteration limit (\(10 n\)), each step runs to that limit, so on such problems the refinement can cost up to about five times the first solve, and the step more costs most: on two badly scaled QPs in single precision (HUES-MOD and QSCFXM1, 9 starts each) the steps took 2.2 times the conjugate gradient iterations they took with a tolerance of \(4 \epsilon\), and the runs 26% more in all, while 15 of the 18 runs solved instead of 9.
Accuracy of each iteration’s solve
The right-hand side of each iteration’s solve changes every iteration, and the solve’s error only matters once it is comparable to SCS’s residuals. So SCS checks it periodically and makes the solves more accurate only while their error would hold the iterates back.
The check. Every 25 iterations SCS computes the residual of that iteration’s solve, \(\|z^k - K u\|_\infty\) with \(K\) the matrix above, and compares it with tol, the smaller of SCS’s own primal and dual residuals at its last convergence check. While refinement is off, the check costs one multiply by \(K\) every 25 iterations.
Rounding level. In double precision refinement is never on while that residual is at rounding level: at most four machine epsilons times \(\|\,|z^k| + |K|\,|u|\,\|_\infty\), the size of the terms the residual is computed from, row by row. A residual that small is mostly the rounding of its own computation, and refinement cannot lower it by more than a small factor. (Four is a bound with room: refined residuals are typically a third to a half of an epsilon of their terms, since the rounding errors of a row’s terms partly cancel.) This matters where tol goes to zero, on an infeasibility or unboundedness certificate that SCS keeps iterating on: with an absolute floor instead (tol at least \(10^{-12}\), as in an earlier rule), which is below rounding level wherever those terms are large, refinement turned on there and stayed on to the end. The size is computed only at a check where it can change the outcome (one pass over \(A\) and \(P\), the cost of a multiply). Single precision has no such test: there refinement also lowers an error of the solution that the residual does not show (with conjugate gradients and the dense solver, which solve a smaller system), and turning it off at rounding level lost problems at \(10^{-6}\). With conjugate gradients, in both precisions, the thresholds do not go below the solvers’ best accuracy (\(10^{-12}\), \(10^{-6}\) in single precision), below which they are never asked to go: refinement does not turn on while the error is at most ten times that, and turns off at the latest once the error is at most that.
Direct solvers (sparse direct, dense, Apple Accelerate, MKL Pardiso, cuDSS). When the residual of a check is above \(0.01\,\) tol, each following iteration solves in correction form: SCS keeps the previous iteration’s solution \(u_0\) and passes it to the linear solve as its warm start, which solves \(K d = z^k - K u_0\) and takes \(u = u_0 + d\). The error of a solve with a factorization is about proportional to the size of the right-hand side it is given. The iterates move little from one iteration to the next, so \(z^k - K u_0\) is \(10^{-3}\) to \(10^{-7}\) of \(z^k\), and \(u\) is that much more accurate than a plain solve, for one more multiply by \(K\) per iteration and no extra solve. The errors do not build up from one iteration to the next: each correction-form solve shrinks the error it inherits by the same factor as it shrinks the right-hand side. When the previous solution is no better a guess than zero (\(\|z^k - K u_0\| \ge \|z^k\|\), which happens after \(R\) changes) that iteration solves plainly. At each check while it is on, SCS also makes a plain solve of the same right-hand side, only to measure its error, and turns the correction form off once that error is at most \(0.001\,\) tol; the iterate stays the correction-form solution, unless the correction-form solution’s own residual (one more multiply by \(K\) per check) is more than twice the plain solve’s and above rounding level (\(10^{-14}\,\|z^k\|_\infty\) in double precision, \(10^{-5}\,\|z^k\|_\infty\) in single). That safeguard is for a factorization so inaccurate that the correction form does not reduce the error; normally the correction-form residual is near rounding level and the safeguard changes nothing.
Why these choices: what slows SCS down is switching between accurate and inexact solves, more than the inexact solves themselves. On QFORPLAN at \(10^{-6}\) with Apple Accelerate, the previous rule (refine only once the error exceeds tol, with one more solve per iteration, until it falls below \(0.1\,\) tol) took 1,300 to 140,900 iterations depending on the starting point, and the correction form with the plain solve put into the iterate at every check (one inexact solve every 25 accurate ones) took up to 31 times the iterations of the rule here, which took 700 to 975. Turning on at \(0.01\,\) tol and off at \(0.001\,\) tol starts the accurate solves before they are needed and keeps them while the residuals fall. Thresholds ten times lower were on for 12.6% of the iterations at the default tolerances instead of 1.3%, and for most of the solve on more problems, with similar results at tight tolerances; ten times higher ones took more iterations on the badly scaled problems.
Indirect solvers (CPU and GPU conjugate gradients). Conjugate gradients already solves to a tolerance tied to SCS’s residuals, and its error is set by that tolerance rather than by the size of the right-hand side, so the correction form would not make it more accurate. What goes wrong is that a solve misses its tolerance: it stops at its iteration limit, the residual it tracks drifts from the true one (in single precision), or \(y\), which it computes from \(x\), carries rounding that its smaller system does not see. When a check finds the residual above tol, each following iteration’s solve also refines itself: it computes the residual of the whole system (one multiply by \(K\)) and, while that is above the conjugate gradient tolerance, solves for it with conjugate gradients from zero, to that tolerance, and adds the correction, keeping each such step only if it lowers the residual, and at most two. So refinement costs one multiply per iteration, and conjugate gradient iterations only where a solve missed its tolerance. At each check while it is on, SCS also makes a plain conjugate gradient solve of the same right-hand side, only to measure its error, and turns refinement off once that error is at most \(0.1\,\) tol, as for the direct solvers. The steps solve for the residual of the whole system: restarting conjugate gradients on the same right-hand side from the solution, the same in exact arithmetic, works with the residual of the smaller system and cannot see all of the rounding error: in single precision it solved 16 of 25 random SOCPs at \(10^{-5}\) instead of 25, in 12 times the time.
What to expect (direct solvers):
At the default tolerances it rarely turns on: on 112 LPs, QPs and SDPs at \(10^{-4}\) and \(10^{-6}\) from 3 starting points each (QDLDL), for 1.3% of the iterations, with the same iterations in 318 of the 336 runs (9 fewer, 9 more) and about 1% more time, within the run-to-run noise.
At tight tolerances it is what lets direct solves converge, and it takes fewer iterations than refining once the error is already too large: on 500 random LPs and SOCPs at \(10^{-9}\) with QDLDL, 2.6% fewer iterations and 2.3% less time; with cuDSS on 200 of them, 7% fewer iterations and 9% less solve time (14% less without Anderson acceleration); with Apple Accelerate, whose solves can be inaccurate on badly scaled problems, on 30 LPs, QPs and SDPs at \(10^{-4}\) and \(10^{-6}\) from 3 starting points each, 0.95 times the time in geometric mean of the per-run ratios, and 0.89 times the shifted geometric mean of the times (shift 10 s), which weighs the long runs more (QFORPLAN at \(10^{-6}\): 700 to 975 iterations, where the previous rule took 1,300 to 140,900 depending on the starting point). On 45 LPs and QPs at \(10^{-8}\) and \(10^{-9}\) with QDLDL the results were the same within noise. MKL Pardiso’s solves are accurate enough that it turns on less often: on 33 LPs and QPs at \(10^{-9}\), in 15 of them, for 3.5% fewer iterations and the same time.
While it is on, an iteration’s linear-system time is about 1.1 to 1.5 times that of a plain one: the extra multiply by \(K\) costs most, relative to the solve, on small and very sparse systems (1.4 with QDLDL on small LPs, 1.1 with Accelerate on larger QPs).
On a problem that stalls it can stay on for most of the remaining iterations: on 26 SDPs and QPs that stall at \(10^{-4}\) to \(10^{-6}\) (78 runs), it was on for 19% of the iterations and for most of the solve in 11 runs, which solved one run more and took 6% more time. In single precision it tends to stay on once it turns on (see “Rounding level” above).
What to expect (indirect solvers):
Refinement is decided only at the checks, as for the direct solvers, so once it turns on it stays on for at least 25 iterations, until a check finds the plain solve within \(0.1\,\) tol.
In double precision it rarely turns on: never on 500 random SOCPs at \(10^{-9}\), for 2% of the iterations on badly scaled LPs and QPs at \(10^{-4}\), and for 13% to 24% on the Netlib and SDPLIB infeasible problems at \(10^{-4}\) and \(10^{-6}\), mostly on certificates that SCS keeps iterating on and on problems that stall. There each iteration with a step costs conjugate gradient solves, and the 25-iteration minimum adds up: an LP run for a fixed 2,000 iterations took 2.3 times as long as with an earlier rule that decided at every iteration while on. Deciding at every iteration was measured too: it cost 2% to 5% more time overall in single precision, where refinement is on most of the time.
In single precision at tight tolerances (\(10^{-6}\)) it is on for 60% to 86% of the iterations of random SOCPs, and it is what lets many of those solves converge. There the outcome of a run can flip with rounding from one starting point to the next.
While it is on, an iteration costs one more multiply by \(K\), and conjugate gradient solves only where its plain solve missed the tolerance (in single precision almost always: 1.5 to 1.8 steps per iteration on average), plus one more plain solve at each check.
Who computes the multiplies. The multiplies by \(K\) are made inside
the linear solve (scs_solve_lin_sys, see Implementing a new linear solver).
With the direct solvers SCS keeps each iteration’s solution and passes it to
the next solve as its warm start; with the indirect solvers it asks for
refinement steps. Per iteration SCS asks for:
Iteration |
Solves |
Multiplies by \(K\) |
|---|---|---|
Off, not a check |
one plain solve (CG: from the warm start) |
none |
Off, a check (every 25) |
one plain solve, with its residual |
1 |
Direct, on, not a check |
one solve warm-started from the previous solution (correction form) |
1 |
Direct, on, a check |
the warm-started solve with its residual, and a plain solve with its residual |
3 |
CG, on, not a check |
CG with refinement steps: its residual and, where the solve missed its tolerance, up to two CG solves from zero for the residual |
1, and 1 per step |
CG, on, a check |
the same, and a plain CG solve with its residual |
2, and 1 per step |
In double precision a check whose residual is above the threshold also makes one pass over \(A\) and \(P\), about the cost of a multiply, for the rounding level (see “Rounding level” above).
By default the multiplies are SCS’s own products with the problem data (the multiply by \(A^\top\) runs on OpenMP’s threads when SCS is built with OpenMP, and stays deterministic: each entry is summed by one thread in a fixed order). MKL Pardiso computes them with MKL’s threaded sparse matrix-vector product instead, and cuDSS from 60,000 nonzeros in \(K\) computes them on the GPU, where the residual stays (the warm start is copied to the GPU). The solve for \((c, -b)\) makes its multiplies the same way. The decisions above are the same either way; only the cost of the multiply and its rounding change.
What the solver’s own multiplies buy is a cheaper iteration while the correction form is on. With cuDSS on 10 large LPs, QPs and SOCPs at \(10^{-8}\) (NVIDIA GB10), such an iteration cost 1.19 times a plain one with the multiplies on the GPU, against 1.48 with SCS’s on the CPU (on BOYD1 1.61 ms against 2.63, a plain iteration taking 1.33; measured while the warm start stayed on the GPU, see Sparse GPU direct method for the cost of copying it). With MKL Pardiso on 33 LPs and QPs at \(10^{-9}\) (4 threads, AMD Zen 3) it cost 1.32 times a plain one against 1.45. Whole solves changed by a few percent at most, within the run-to-run variation of the iteration counts, because the correction form is on for a small part of most solves.
Available linear solvers
Each of the below linear solvers is included in their own binary. If linking against SCS directly, then to switch between them you must compile and link against the right binary. If calling SCS via one of the interfaces then you can choose between the different linear solvers using the appropriate settings.
Sparse direct
The direct method is the default linear system solver in SCS and factorizes the above matrix using a sparse permuted LDL factorization. Then it solves the linear system at each iteration using the cached factors. Since the linear system is quasidefinite we have strong existence guarantees about the factorization. It relies on the external (but included) AMD and QDLDL packages.
Dense direct
The dense direct method reduces the KKT system to the smaller Gram matrix
\(G = R_x + P + A^\top R_y^{-1} A\) (size \(n \times n\)) and
factorizes it using the LAPACK dpotrf (Cholesky) routine. The
\(A^\top R_y^{-1} A\) product is computed via dsyrk and subsequent
solves use dpotrs. When the diagonal \(R\) changes, the Gram matrix is
re-formed and re-factorized.
This backend is best suited for small to medium-sized problems where the
constraint matrix \(A\) is dense. For such problems, dense BLAS/LAPACK
routines can outperform sparse solvers due to highly optimized memory access
patterns and lower overhead. It requires LAPACK (USE_LAPACK=1).
MKL Pardiso
The Intel MKL Pardiso solver is a shared-memory multiprocessing parallel direct sparse solver which is included Intel oneAPI MKL library. This offers an alternative to the single threaded AMD / QDLDL libraries which come bundled with SCS. Pardiso tends to be faster than AMD / QDLDL, especially for larger problems. If MKL is installed on your system then it is generally worth using MKL for both the blas / lapack usage as well as the linear system solve. Intel MKL is now available for free and without restrictions for everyone, though it only offers limited support for non-Intel CPUs. The x86-64 manylinux Python wheels include it, statically linked (see Python).
Threads. With a threaded MKL, Pardiso runs on MKL’s threads
(MKL_NUM_THREADS, else OMP_NUM_THREADS): the reordering, the
factorization and the solve done in every iteration, which SCS asks Pardiso to
run in parallel. Starting and synchronizing
the threads costs a few tens of microseconds per call, which on a small linear system
is more than the work. So SCS runs Pardiso on one thread when the factor
Pardiso computes has fewer than 50,000 nonzeros (PARDISO_MIN_THREADED_NNZ
in linsys/mkl/direct/private.c). The choice is made once, at setup, from
the problem data and the ordering Pardiso computes; all the Pardiso calls of a
solve then use the same thread count, and MKL’s BLAS and LAPACK keep their
threads. On 4 threads, small problems iterated up to about 2x faster this
way with MKL_DYNAMIC=FALSE, and up to about 1.3x with MKL’s default
(dynamic mode, which already runs the smallest systems on one thread by
itself); larger ones were unaffected. The break-even point depends on the
problem and the machine; in our measurements it was between about 30,000 and
60,000 factor nonzeros. A sequential MKL, such as the one in the Python
wheels, always runs on one thread, so there this changes nothing. On small
problems a sequential MKL is still faster than a threaded one, because a
threaded MKL costs more per call even on one thread. On several threads
Pardiso may round differently from run to run, so two runs of the same problem
can differ slightly in their results and iteration counts.
Multiplies for the refinement. MKL Pardiso computes the multiplies by
\(K\) of the per-iteration refinement (see Accuracy of each iteration’s solve) with MKL’s
sparse BLAS, on the same upper triangle Pardiso factorizes, analysed once at
setup (mkl_sparse_optimize). They run on MKL’s threads, or on one thread
when Pardiso does (the rule above), so that a solve never mixes thread counts.
Measured per multiply against SCS’s own single-threaded product (AMD Zen 3, 4
threads, 46 LPs and QPs): 0.2 to 0.5 times the time where it runs on MKL’s
threads (0.76 against 2.39 ms on co-100), and 0.45 to 0.93 times where it runs
on one thread; forcing 4 threads on the smallest systems made it about twice
as slow as one thread. In the solves, an iteration with the correction form
on cost 1.32 times a plain one, against 1.45 with SCS’s product (33 LPs and QPs
at \(10^{-9}\)). The products add no run-to-run variation of their own:
with the same number of threads they gave the same bits in repeated runs (a
different thread count can change their last bits). The products also cost
setup time that has not been measured: MKL analyses \(K\)
(mkl_sparse_optimize) at setup and again at every update of \(R\),
whether or not the correction form ever turns on, since the check every 25
iterations uses the product too. In a build with DLONG but 32-bit MKL
integers, a \(K\) too large for those integers (more than \(2^{31}\)
stored nonzeros) gets SCS’s own products instead; BLAS64=1 (Meson’s
use_blas64) provides MKL’s at any size. If they cannot be set up
otherwise (out of memory), setup fails with a message. Built with
make mkl MKL_NO_OWN_PRODUCTS=1 (see Compile flags), MKL Pardiso
uses SCS’s products at every size; that is slower (1.45 instead of 1.32
times a plain iteration while the correction form is on), and the CI uses it
so that this path stays tested.
Apple Accelerate
The Apple Accelerate framework provides a sparse LDLT factorization that is optimized for Apple hardware (including Apple Silicon). This backend uses the unpivoted LDLT solver from the Accelerate Sparse Solvers API, which is well-suited for the quasi-definite KKT systems that SCS produces. Accelerate performs its own fill-reducing ordering internally so no external AMD package is needed.
This backend is macOS-only and is available without installing any additional
libraries since the Accelerate framework ships with Xcode / the macOS SDK.
It does not support 64-bit integer indexing (DLONG).
To build with Make:
make accelerate
To build with CMake:
cmake -DUSE_APPLE_ACCELERATE=ON ..
In Python, the Accelerate backend is included automatically on macOS
(pip install scs is sufficient). On macOS,
linear_solver=scs.LinearSolver.AUTO selects the bundled QDLDL; select
Accelerate explicitly with:
solver = scs.SCS(data, cone, linear_solver=scs.LinearSolver.ACCELERATE)
Sparse indirect
The indirect method solves the above linear system approximately with a ‘matrix-free’ method. To do this it first reduces the system to solving
then solves the positive definite system using using conjugate gradients. Each iteration of
CG requires one multiply each of sparse matrices \(P, A, A^\top\). The
system is solved up to some tolerance, which is tuned to ensure that the
overall algorithm converges: each solve targets a small fraction
(CG_TOL_FACTOR, default \(0.03\)) of the smaller of the current
primal and dual residuals, additionally capped by a term decaying with
iteration \(k\) like \(O(1/k^\gamma)\) where \(\gamma\) is
determined by the constant CG_RATE (defaults to \(2\)), and
floored at CG_BEST_TOL. Each solve is warm-started from the previous
solution. The solver also harvests approximate eigenvectors of the reduced
matrix from the CG iterations themselves (eigCG; Stathopoulos and Orginos
2010) and uses up to DEFLATE_VECTORS (default 30) of them to deflate
the smallest eigenvalues from subsequent solves, which substantially reduces
the CG iterations needed on ill-conditioned problems. Applying the deflation
in a solve costs no matrix multiplies. Each harvest costs the multiplies of
one CG iteration per vector.
Deflation needs LAPACK and double precision. It is switched off when SCS is
built without LAPACK (USE_LAPACK=0) or in single precision
(SFLOAT=1), and only the CPU indirect solver has it. Single precision
builds also use \(0.2\) for CG_TOL_FACTOR and \(1.5\) for
CG_RATE.
Deflation keeps \(2n\) numbers per vector in memory (\(60n\) by
default), and a harvest takes a further \(n\) numbers per window entry and
\(2n\) per vector while it runs (\(150n\) by default). That is much
more than CG itself needs (a few vectors of length \(n\)). Two constants
in include/glbopts.h set it, and both are fixed when SCS is compiled:
DEFLATE_VECTORS(default 30) is the number of deflation vectors. More vectors take more of the smallest eigenvalues out of the solves, for more memory and more work per solve.0turns deflation off, which gives plain preconditioned CG with no extra memory.EIGCG_WINDOW(default 60) is the size of the eigCG window, the number of CG vectors that a harvest keeps in memory. A larger window compresses the CG history less often, for more memory while the harvest runs. The window is never smaller than three times the number of deflation vectors, so with the default 30 vectors it is 90 and a smallerEIGCG_WINDOWhas no effect unlessDEFLATE_VECTORSis lowered as well.
To change them, define them when compiling. With the Makefile, pass them in
CFLAGS and rebuild from scratch (make purge first, since
make does not rebuild objects when only the flags change):
make purge
make CFLAGS="-DDEFLATE_VECTORS=0"
With CMake, pass them in CMAKE_C_FLAGS when configuring:
cmake -DCMAKE_C_FLAGS="-DDEFLATE_VECTORS=10 -DEIGCG_WINDOW=40" ..
A negative value stops the compilation with an error. Lowering
DEFLATE_VECTORS, or setting it to 0, is the way to save memory with the
indirect solver on a problem where \(n\) is very large. See also
Compile flags.
The indirect method has the advantage of not requiring an expensive factorization but typically is slower on a per-iteration basis. In most cases the factorization is relatively cheap so the direct method is the default, however for very large problems the indirect solver can be faster.
Sparse GPU indirect method
The above linear solvers all run on CPU. We also have support for a GPU version
of the indirect solver, where the matrix multiplies are all performed on the
GPU. It runs conjugate gradients with the same diagonal preconditioner,
tolerance schedule and warm start as the CPU indirect solver, but it does not
harvest eigenvectors or deflate, so DEFLATE_VECTORS and
EIGCG_WINDOW have no effect on it. Usually the direct GPU solver will be faster than this solver.
Sparse GPU direct method
This is a linear solver that uses the cuDSS library to solve the linear system on the GPU. It is similar to the direct solver, but uses the calls to cuDSS library to perform the analysis, numerical (re-)factorization and subsequent solves. According to its documentation reordering (a major part of the analysis phase) is executed on the host while symbolic factorization (another part of the analysis phase), numerical factorization, and solve are executed on the GPU.
SCS runs cuDSS without pivoting, matching or iterative refinement, so it computes a plain LDL’ factorization, as the CPU direct solver does. The linear system is quasi-definite, so this factorization exists under any ordering, and each iteration costs one solve. From version 1.0, cuDSS by default applies a matching to a symmetric indefinite matrix. With its default pivoting that makes the factorization up to four times larger (2.4 times larger on average on the LPs and QPs measured), and without pivoting it made the solves inaccurate enough for SCS to stall on some LPs. Older versions of cuDSS do not apply a matching unless asked to, so SCS factorizes the same way with every cuDSS version it supports. The tradeoff is that the accuracy of a solve rests on the conditioning of the system: the worst relative residual of a solve in the test suite was about 6e-8, against 5e-11 with cuDSS’s default pivoting and matching. Single-precision builds keep one step of iterative refinement per solve, which about doubles the cost of a solve, because without it one problem in the test suite does not converge.
Multiplies for the refinement. When \(K\) has at least 60,000 nonzeros
(CUDSS_MIN_PRODUCT_NNZ in include/glbopts.h; set it with
make cudss CUDSS_MIN_PRODUCT_NNZ=..., see Compile flags), the cuDSS
solver computes the multiplies by \(K\) of the per-iteration refinement
(see Accuracy of each iteration’s solve) on the GPU: one cuSPARSE sparse matrix-vector product
and one cuBLAS reduction. The residual stays on the GPU; the warm start, the
previous solution that SCS keeps on the host, is copied to the GPU once per
iteration with the correction form on, one vector of \(n + m\) numbers
more than a plain solve copies. cuSPARSE has no symmetric product, so \(K\)
is stored a second time with both triangles, about twice the nonzeros of the
copy cuDSS factorizes. A call costs about 0.04 ms whatever the size, so smaller
systems use SCS’s product on the CPU, which was faster there. On an NVIDIA
GB10, per multiply, the GPU took 0.12 to 0.37 times the CPU’s time above
\(3.7 \cdot 10^5\) nonzeros (0.18 against 1.27 ms on BOYD1).
In the solves, on 10 large LPs, QPs and SOCPs at \(10^{-8}\), an
iteration with the correction form on cost 1.19 times a plain one, against
1.48 with the multiplies on the CPU, and the time per iteration fell by 4%.
That was measured with the warm start kept on the GPU. Copying it from the
host, as now, added 0.02 to 0.12 ms to such a solve on the same problems (2
to 9% of a plain solve): an estimated 0.14% of their total solve time, and at
most 3.3% on one (UBH1, with the correction form on for 64% of its
iterations). On a discrete GPU, where the copy crosses PCIe, it has not been
measured.
Setting them up (building \(K\) with both triangles, copying it to the
GPU, creating the cuSPARSE and cuBLAS handles) is done at setup whether or not
the correction form ever turns on, since the check every 25 iterations uses
the multiply too. On the GB10 it took 3, 35 and 340 ms for random \(K\)
with \(10^5\), \(10^6\) and \(8 \cdot 10^6\) nonzeros, 5 to 13%
of the time cuDSS’s own setup (analysis and factorization) took; the two
handles took 0.4 to 0.8 ms of that. If they cannot be set up (out of GPU
memory, or a \(K\) too large for 32-bit indices in a build without
DLONG), setup fails with a message.
Reproducibility of the GPU solvers
With either GPU solver, two runs of the same problem on the same machine are
not guaranteed to give bit for bit the same result. The GPU indirect solver
does its sparse matrix-vector products with cuSPARSE’s
CUSPARSE_SPMV_CSR_ALG1, which cuSPARSE does not guarantee to give the
same bits on every run, and SCS runs cuDSS without its deterministic mode
(CUDSS_CONFIG_DETERMINISTIC_MODE), which made LPs and QPs several times
slower to solve on an NVIDIA GB10. SCS has no setting to change either choice.
The multiplies of the refinement on the GPU (cuDSS, see above) use
CUSPARSE_SPMV_CSR_ALG2, which gives the same result every run, so they
add no variation of their own. When two runs differ, their iterates differ
slightly. Printed values that are small near the end of a solve, such as the
dual residual and the gap, can then differ in every digit, and the iteration
count can change if a residual ends close to its tolerance. In a check on an
NVIDIA GB10 (CUDA 13.0, cuDSS 1.0.0), three runs of a random SOCP with each GPU
solver all took 150 iterations, and their last iterations differed in the dual
residual and the gap (the gap of the GPU indirect solver by a factor of 13).
Implementing a new linear solver
A linear solver implements the struct ScsLinSysWork, which holds its
workspace, and the five functions in include/linsys.h (documented
below); the linsys directory has seven worked examples. Four are
simple: set up (for instance factorize \(K\)), update for a new
\(R\), free, and name. The fifth, scs_solve_lin_sys, solves
\(K x = b\) and also takes a warm start, a tolerance and a number of
refinement steps, and reports the residual \(\|b - K x\|_\infty\):
SCS’s Iterative refinement runs through it. The solvers in
linsys write only their plain solve and get the rest from a shared
routine (linsys/scs_matrix.h). A new solver built with SCS’s sources
does the same in five steps:
#include "scs_matrix.h"and put aScsLinSysShared sh;member in yourScsLinSysWork.Write your plain solve, which overwrites
bwith \(K^{-1} b\) and returns 0 (nonzero on failure). A direct solver ignoressandtol; an iterative one starts froms(its first \(n\) entries; from zero when it isSCS_NULL) and stops attol:static scs_int plain_solve(ScsLinSysWork *w, scs_float *b, const scs_float *s, scs_float tol);
At the end of
scs_init_lin_sys_work, after your own setup:if (SCS(lin_sys_shared_init)(&w->sh, A, P, diag_r, 0, plain_solve, SCS_NULL, SCS_NULL) != 0) { scs_free_lin_sys_work(w); return SCS_NULL; }
with 1 in place of the first 0 for an iterative solver such as conjugate gradients (its warm start is then the solver’s starting point, and each refinement step a solve from zero of the residual, computed in the full space; see
linsys.h). This allocates three vectors of \(n + m\) numbers and keeps the three pointers: SCS keepsA,Panddiag_ralive untilscs_free_lin_sys_work, leavesAandPunchanged and writes each new \(R\) into the samediag_r, and the residuals are computed from them.Implement
scs_solve_lin_sysas one call:scs_int scs_solve_lin_sys(ScsLinSysWork *w, scs_float *b, const scs_float *s, scs_float tol, scs_int max_refine_steps, scs_float *res) { return SCS(lin_sys_shared_solve)(&w->sh, w, b, s, tol, max_refine_steps, res); }
Call
SCS(lin_sys_shared_free)(&w->sh)inscs_free_lin_sys_work(it is safe on a zeroedsh).
With that, SCS’s refinement behaves with your solver as with the bundled
ones: the warm start (the correction form and its comparison with zero, or
the starting point of an iterative solver), the refinement steps, and the
residuals are the shared routine’s, with SCS’s own
multiplies by \(K\) from the problem data. Only your plain solve’s
accuracy and cost differ. linsys/scs_matrix.h is not installed with
SCS’s headers, so this is for solvers compiled with SCS’s sources, as every
solver outside this repository we know of is.
Your own multiplies (optional). A solver that holds \(K\) anyway can
compute the multiplies with its own copy instead, for instance with a
threaded sparse matrix-vector product, by passing a residual function in
place of the first SCS_NULL in step 3:
static scs_int my_residual(ScsLinSysWork *w, const scs_float *b,
const scs_float *x, scs_float *r,
scs_float *nr, scs_float *nb);
It computes \(r = b - K x\) with your \(K\) (as of the last update of
\(R\)) into r, \(\|r\|_\infty\) in *nr and
\(\|b\|_\infty\) in *nb (unless nb is
SCS_NULL), and returns 0 (nonzero on failure, which fails the solve
with a message asking to open an issue). MKL Pardiso does this with MKL’s
sparse BLAS (prod_residual in linsys/mkl/direct/private.c). A
solver whose vectors live elsewhere can also pass a correct function in place
of the second SCS_NULL:
static scs_int my_correct(ScsLinSysWork *w, const scs_float *x,
const scs_float *r, scs_float *out);
It sets out to \(x + K^{-1} r\), where r is that of the
residual call the shared routine always makes just before and x has
the values of that call’s x. So the residual function may keep
\(r\) where the solver keeps its vectors, and need not write the
r it is given; if it keeps \(x\) too, it keeps a copy, not the
pointer: x may then be another vector with the same values, and
out the very vector the residual call was given as x. cuDSS does
this on the GPU (dev_residual and dev_correct in
linsys/cudss/direct/private.c), so that the residual never leaves
the device. Decide whether to use your own multiplies once, in
scs_init_lin_sys_work, by a rule you state up front (MKL: always,
except a \(K\) too large for 32-bit MKL integers in a DLONG build
without BLAS64; cuDSS: from CUDSS_MIN_PRODUCT_NNZ nonzeros),
never by whether memory or a library happened to be available: if they
should be used but cannot be set up, make scs_init_lin_sys_work fail
with a message saying why.
Without the shared routine. A solver may implement
scs_solve_lin_sys entirely itself, but then it must honour the whole
of linsys.h. res must be the true residual of the returned
\(x\), because SCS turns its refinement on and off by comparing it with
its own residuals. A direct solver given s must return the
correction form from it, and solve plainly when \(\|b - K s\|_\infty
\ge \|b\|_\infty\). With max_refine_steps above 0 it must take at most
that many steps \(x + K^{-1}(b - K x)\) (a CG solver too, with the
residual computed in the full space and solved from zero), keep a step only
if it lowers the residual, and stop after one that does not halve it. SCS
asks for such steps to solve for \((c, -b)\) (see The solve for (c, -b)),
and stops with an error if that solve fails. A direct solver that ignores
s still gives correct answers, but SCS’s refinement then cannot make
its solves more accurate, which on badly scaled problems can keep SCS from
reaching tight tolerances.
Tests. test_lin_sys_solve in the test suite checks the contract
against residuals it computes itself: warm starts near and far from the
solution (the correction form and its fallback), refinement and its limits
(steps kept only when better, the halving stop, max_refine_steps),
and the residual with the \(K\) of the solver’s rule,
before and after an update of \(R\). test_refine_perturbed makes
the solver factorize a different \(R\) from the one SCS measures with, so
that SCS’s refinement fires (and, with a mismatch too large to contract, its
safeguard); a solver that measures with its own \(K\) follows the update,
sees no mismatch, and is skipped there with a message (MKL Pardiso, unless
built with MKL_NO_OWN_PRODUCTS; cuDSS from CUDSS_MIN_PRODUCT_NNZ
nonzeros). test_g_accuracy checks that the solve for
\((c, -b)\) reaches machine precision on a badly scaled problem, and
that a solver given a far different \(R\) (skipped likewise) makes SCS
stop with SCS_FAILED and the message asking to open an issue.
From SCS 3.3. The solve was scs_solve_lin_sys(w, b, s, tol).
max_refine_steps and res are new, so a solver written for 3.3
no longer compiles. Rename its solve plain_solve (it keeps its 3.3
meaning) and follow the steps above; the solver then behaves as the bundled
solvers do. A solver written against the unreleased development versions
after 3.3, which had scs_lin_sys_residual, scs_lin_sys_keep and
scs_lin_sys_correct, deletes them; its own multiplies, if it has
them, become a residual function as above.
-
typedef struct SCS_LIN_SYS_WORK ScsLinSysWork
Struct containing linear system workspace. Implemented by linear solver.
Functions
-
ScsLinSysWork *scs_init_lin_sys_work(const ScsMatrix *A, const ScsMatrix *P, const scs_float *diag_r)
Initialize
ScsLinSysWorkstructure and perform any necessary preprocessing (for instance factorize K, seescs_solve_lin_sys).The solver may keep the three pointers and read the arrays in any later call: they stay valid, and A and P unchanged, until
scs_free_lin_sys_work, and SCS writes every new R into this samediag_rarray before it callsscs_update_lin_sys_diag_r.- Parameters:
A –
Adata matrix,m x n.P –
Pdata matrix,n x n, upper triangle, orSCS_NULL.diag_r –
R > 0diagonal entries of lengthm + n.
- Returns:
Linear system solver workspace, or
SCS_NULLon failure (with a message saying why).
-
void scs_free_lin_sys_work(ScsLinSysWork *w)
Frees
ScsLinSysWorkstructure and associated allocated memory.- Parameters:
w – Linear system private workspace.
-
scs_int scs_solve_lin_sys(ScsLinSysWork *w, scs_float *b, const scs_float *s, scs_float tol, scs_int max_refine_steps, scs_float *res)
Solves the linear system as required by SCS:
\[\begin{split} K x = b, \qquad K = \begin{bmatrix} (R_x + P) & A^\top \\ A & -R_y \\ \end{bmatrix} \end{split}\]for
x, wherediag(R_x, R_y) = Ris the one given to the lastscs_update_lin_sys_diag_r(or toscs_init_lin_sys_work), and overwritesbwithx. Withmax_refine_steps0 andresSCS_NULLthis is the solve of SCS 3.3 for a CG solver (conjugate gradients fromstotol), and for a direct solver given nos(a plain solve).Direct solvers (a factorization: QDLDL, dense, Apple Accelerate, MKL Pardiso, cuDSS):
Warm start. Given
s, the solver computes \(r = b - K s\) and, if \(\|r\|_\infty < \|b\|_\infty\), returns the correction form \(x = s + K^{-1} r\), whose error is about that of a plain solve times \(\|r\|_\infty / \|b\|_\infty\), for one multiply by K more. Otherwise (s is no better a guess than zero, for instance after R changed) it solves plainly, \(x = K^{-1} b\).Refinement, if
max_refine_steps> 0: while \(\|b - K x\|_\infty\) >toland fewer thanmax_refine_stepssteps were taken, the candidate \(c = x + K^{-1}(b - K x)\) replaces x if its residual is strictly smaller; if not, x stays and refinement stops. It also stops after a kept step that did not at least halve the residual. Each step costs a solve and a multiply by K, the first one a multiply more (the residual of x).
CG solvers (conjugate gradients on the reduced system, CPU and GPU):
CG from
s(its first n entries; y is computed from x), or from zero, until the residual CG tracks is belowtol.Refinement, if
max_refine_steps> 0: as for the direct solvers, with \(K^{-1}(b - K x)\) a CG solve from zero totol. The residual is computed in the full space with the multiplies below: the one CG tracks, on the reduced system, can drift from it (in single precision or from a warm start far from x) and has a higher rounding floor, and y is computed from x, so restarting CG on b from x would remove only part of either. Each step costs CG iterations and a multiply by K.
The multiplies by K (warm start, refinement,
res) use the solver’s own copy of K where it has one, by a rule fixed whenscs_init_lin_sys_workreturns and stated in the solver’s documentation (MKL Pardiso; cuDSS fromCUDSS_MIN_PRODUCT_NNZnonzeros), else SCS’s products with the A, P and diag_r given toscs_init_lin_sys_work. Every decision compares residuals, never timings: a call is deterministic whenever the solver’s plain solve and products are.- Parameters:
w – Linear system private workspace.
b – Right-hand side, n + m entries; overwritten with the solution.
s – Warm start, a guess of the solution (n + m entries; CG reads the first n), or
SCS_NULL. Not changed; must not aliasb.tol – The accuracy asked for, as \(\|b - K x\|_\infty\). CG solvers stop at it, also below 1e-12 (smaller is more accurate and costs more CG iterations), and their refinement steps solve to it; they need
tol> 0, and return x = 0 without iterating when \(\|b\|_\infty \le \min(\mathrm{tol}, 10^{-12})\). Direct solvers refine toward it, and ignore it whenmax_refine_stepsis 0. Below the rounding level of the residual (at most a few machine epsilons times \(\| |b| + |K|\,|x| \|_\infty\), absolute values entry by entry, and typically a third of one, since the rounding errors of a row’s terms partly cancel) a step only measures rounding, and the halving test stops it.max_refine_steps – At most this many refinement steps; 0 for none.
res – If not
SCS_NULL, set to \(\|b - K x\|_\infty\) for the returned x and the given b, with the multiplies above. Cost: a copy of b and a multiply by K, unless refinement computed it. Asking for it never changes x. A NaN entry of the residual may be missed by the max (as by SCS’snorm_inf), so a finite*resdoes not show that x is finite.
- Returns:
0 on success; nonzero if a solve or a multiply failed (b and
*resare then unspecified).
-
scs_int scs_update_lin_sys_diag_r(ScsLinSysWork *w, const scs_float *new_diag_r)
Update the linsys workspace when
Ris changed. For example, a direct method for solving the linear system might need to update the factorization of the matrix. SCS passes thediag_rarray given toscs_init_lin_sys_work, with the new R written into it.- Parameters:
w – Linear system private workspace.
new_diag_r – Updated
diag_r, diagonal entries of R.
- Returns:
status != 0 indicates failure.
-
const char *scs_get_lin_sys_method(void)
Name of the linear solver.
- Returns:
name of method.