Search

Randomized linear solvers randomly compress and solve a linear system with compelling theoretical convergence rates and computational complexities. However, such solvers suffer a substantial disconnect between their theoretical rates and actual efficiency in practice. Fortunately, these solvers are quite flexible and can be adapted to specific problems and computing environments to ensure high efficiency in practice, even at the cost of lower effectiveness (i.e., having a slower theoretical rate of convergence). While highly efficient adapted solvers can be readily designed by application experts, will such solvers still converge and at what rate? To answer this, we distill three general criteria for randomized adaptive solvers, which, as we show, will guarantee a worst-case exponential rate of convergence of the solver applied to consistent and inconsistent linear systems irrespective of whether such systems are over-determined, under-determined or rank-deficient. As a result, we enable application experts to design randomized adaptive solvers that achieve efficiency and can be verified for effectiveness using our theory. We demonstrate our theory on twenty-six solvers, nine of which are novel or novel block extensions of existing methods to the best of our knowledge., Comment: 44 pages, 5 figures, 3 Tables

Deterministic and randomized, row-action and column-action linear solvers have become increasingly popular owing to their simplicity, low computational and memory complexities, and ease of composition with other techniques. Moreover, in order to achieve high-performance, such solvers must often be adapted to the given problem structure and to the hardware platform on which the problem will be solved. Unfortunately, determining whether such adapted solvers will converge to a solution has required equally unique analyses. As a result, adapted, reliable solvers are slow to be developed and deployed. In this work, we provide a general set of assumptions under which such adapted solvers are guaranteed to converge with probability one, and provide worst case rates of convergence. As a result, we can provide practitioners with guidance on how to design highly adapted, randomized or deterministic, row-action or column-action linear solvers that are also guaranteed to converge.