No Arabic abstract
Based on the geometric {it Triangle Algorithm} for testing membership of a point in a convex set, we present a novel iterative algorithm for testing the solvability of a real linear system $Ax=b$, where $A$ is an $m times n$ matrix of arbitrary rank. Let $C_{A,r}$ be the ellipsoid determined as the image of the Euclidean ball of radius $r$ under the linear map $A$. The basic procedure in our algorithm computes a point in $C_{A,r}$ that is either within $varepsilon$ distance to $b$, or acts as a certificate proving $b ot in C_{A,r}$. Each iteration takes $O(mn)$ operations and when $b$ is well-situated in $C_{A,r}$, the number of iterations is proportional to $log{(1/varepsilon)}$. If $Ax=b$ is solvable the algorithm computes an approximate solution or the minimum-norm solution. Otherwise, it computes a certificate to unsolvability, or the minimum-norm least-squares solution. It is also applicable to complex input. In a computational comparison with the state-of-the-art algorithm BiCGSTAB ({it Bi-conjugate gradient method stabilized}), the Triangle Algorithm is very competitive. In fact, when the iterates of BiCGSTAB do not converge, our algorithm can verify $Ax=b$ is unsolvable and approximate the minimum-norm least-squares solution. The Triangle Algorithm is robust, simple to implement, and requires no preconditioner, making it attractive to practitioners, as well as researchers and educators.
We propose a deterministic Kaczmarz method for solving linear systems $Ax=b$ with $A$ nonsingular. Instead of using orthogonal projections, we use reflections in the original Kaczmarz iterative method. This generates a series of points on an $n$-sphere $S$ centered at the solution $x_*=A^{-1}b$. We show that these points are nicely distributed on $S$. Taking the average of several points will lead to an effective approximation to the solution. We will show how to choose these points efficiently. The numerical tests show that in practice this deterministic scheme converges much faster than we expected and can beat the (block) randomized Kaczmarz methods.
In latest years, several advancements have been made in symbolic-numerical eigenvalue techniques for solving polynomial systems. In this article, we add to this list by reducing the task to an eigenvalue problem in a considerably faster and simpler way than in previous methods. This results in an algorithm which solves systems with isolated solutions in a reliable and efficient way, outperforming homotopy methods in overdetermined cases. We provide an implementation in the proof-of-concept Julia package EigenvalueSolver.jl.
With a quite different way to determine the working rows, we propose a novel greedy Kaczmarz method for solving consistent linear systems. Convergence analysis of the new method is provided. Numerical experiments show that, for the same accuracy, our method outperforms the greedy randomized Kaczmarz method and the relaxed greedy randomized Kaczmarz method introduced recently by Bai and Wu [Z.Z. BAI AND W.T. WU, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), pp. A592--A606; Z.Z. BAI AND W.T. WU, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83 (2018), pp. 21--26] in term of the computing time.
The famous greedy randomized Kaczmarz (GRK) method uses the greedy selection rule on maximum distance to determine a subset of the indices of working rows. In this paper, with the greedy selection rule on maximum residual, we propose the greedy randomized Motzkin-Kaczmarz (GRMK) method for linear systems. The block version of the new method is also presented. We analyze the convergence of the two methods and provide the corresponding convergence factors. Extensive numerical experiments show that the GRMK method has almost the same performance as the GRK method for dense matrices and the former performs better in computing time for some sparse matrices, and the blo
In this paper, combining count sketch and maximal weighted residual Kaczmarz method, we propose a fast randomized algorithm for large overdetermined linear systems. Convergence analysis of the new algorithm is provided. Numerical experiments show that, for the same accuracy, our method behaves better in computing time compared with the state-of-the-art algorithm.