Linear System Solver

At each iteration \(k\) SCS solves the following set of linear equations:

\[\begin{split}\begin{bmatrix} R_x + P & A^\top \\ A & -R_y \\ \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} z^k_x \\ z^k_y \end{bmatrix}\end{split}\]

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,

\[\|(c, -b) - K g\|_\infty \le \tfrac{1}{4} \epsilon \, \big\| |(c, -b)| + |K|\,|g_0| \big\|_\infty\]

(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

\[\begin{split}(R_x + P + A^\top R_y^{-1} A) x & = z^k_x + A^\top R_y^{-1} z^k_y \\ y & = R_y^{-1}(A x - z^k_y).\end{split}\]

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. 0 turns 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 smaller EIGCG_WINDOW has no effect unless DEFLATE_VECTORS is 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:

  1. #include "scs_matrix.h" and put a ScsLinSysShared sh; member in your ScsLinSysWork.

  2. Write your plain solve, which overwrites b with \(K^{-1} b\) and returns 0 (nonzero on failure). A direct solver ignores s and tol; an iterative one starts from s (its first \(n\) entries; from zero when it is SCS_NULL) and stops at tol:

    static scs_int plain_solve(ScsLinSysWork *w, scs_float *b,
                               const scs_float *s, scs_float tol);
    
  3. 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 keeps A, P and diag_r alive until scs_free_lin_sys_work, leaves A and P unchanged and writes each new \(R\) into the same diag_r, and the residuals are computed from them.

  4. Implement scs_solve_lin_sys as 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);
    }
    
  5. Call SCS(lin_sys_shared_free)(&w->sh) in scs_free_lin_sys_work (it is safe on a zeroed sh).

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 ScsLinSysWork structure and perform any necessary preprocessing (for instance factorize K, see scs_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 same diag_r array before it calls scs_update_lin_sys_diag_r.

Parameters:
  • A – A data matrix, m x n.

  • P – P data matrix, n x n, upper triangle, or SCS_NULL.

  • diag_r – R > 0 diagonal entries of length m + n.

Returns:

Linear system solver workspace, or SCS_NULL on failure (with a message saying why).

void scs_free_lin_sys_work(ScsLinSysWork *w)

Frees ScsLinSysWork structure 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, where diag(R_x, R_y) = R is the one given to the last scs_update_lin_sys_diag_r (or to scs_init_lin_sys_work), and overwrites b with x. With max_refine_steps 0 and res SCS_NULL this is the solve of SCS 3.3 for a CG solver (conjugate gradients from s to tol), and for a direct solver given no s (a plain solve).

Direct solvers (a factorization: QDLDL, dense, Apple Accelerate, MKL Pardiso, cuDSS):

  1. 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\).

  2. Refinement, if max_refine_steps > 0: while \(\|b - K x\|_\infty\) > tol and fewer than max_refine_steps steps 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):

  1. CG from s (its first n entries; y is computed from x), or from zero, until the residual CG tracks is below tol.

  2. Refinement, if max_refine_steps > 0: as for the direct solvers, with \(K^{-1}(b - K x)\) a CG solve from zero to tol. 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 when scs_init_lin_sys_work returns and stated in the solver’s documentation (MKL Pardiso; cuDSS from CUDSS_MIN_PRODUCT_NNZ nonzeros), else SCS’s products with the A, P and diag_r given to scs_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 alias b.

  • 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 when max_refine_steps is 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’s norm_inf), so a finite *res does not show that x is finite.

Returns:

0 on success; nonzero if a solve or a multiply failed (b and *res are then unspecified).

scs_int scs_update_lin_sys_diag_r(ScsLinSysWork *w, const scs_float *new_diag_r)

Update the linsys workspace when R is changed. For example, a direct method for solving the linear system might need to update the factorization of the matrix. SCS passes the diag_r array given to scs_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.