The Kaczmarz method is an iterative method for solving large systems of equations that projects iterates orthogonally onto the solution space of each equation. In contrast to direct methods such as Gaussian elimination or QR-factorization, this algorithm is efficient for problems with sparse matrices, as they appear in constraint-based user interface (UI) layout specifications. However, the Kaczmarz method as described in the literature has its limitations: it considers only equality constraints and does not support soft constraints, which makes it inapplicable to the UI layout problem. In this paper we extend the Kaczmarz method for solving specifications containing soft constraints, using the prioritized IIS detection algorithm. Furthermore, the performance and convergence of the proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods offer improvements in performance over standard methods like Matlab's LINPROG, a well-known efficient linear programming solver.
Different direct and iterative methods exist which can solve least-squares problems. Examples of direct methods are QR-factorization @cite_26 and normal equations @cite_50 . Iterative methods that are used to solve linear systems include simplex @cite_41 , revised simplex @cite_46 , conjugate gradient @cite_58 , generalized minimal residual @cite_40 , and others @cite_35 . In order to solve over-determined systems in a least-squares sense, Herman adds some additional constraints and variables, similar to slack variables in the simplex approach @cite_1 . The resulting method converges towards the least-squares solution. Popa analyzed a similar approach for solving least-squares problems @cite_16 @cite_17 . Censor showed that if the relaxation parameter goes to zero then the Kaczmarz method converges to a weighted least-squares solution for inconsistent systems @cite_55 .
@cite_35 @cite_26 @cite_41 @cite_55 @cite_1 @cite_16 @cite_40 @cite_50 @cite_46 @cite_58 @cite_17
1546004968 1485446097 2010440992 2140153041 1968902264 2316564661 1967981081
Preface Acknowledgements 1. Direct solution methods 2. Theory of matrix eigenvalues 3. Positive definite matrices, Schur complements, and generalized eigenvalue problems 4. Reducible and irreducible matrices and the Perron-Frobenius theory for nonnegative matrices 5. Basic iterative methods and their rates of convergence 6. M-matrices, convergent splittings, and the SOR method 7. Incomplete factorization preconditioning methods 8. Approximate matrix inverses and corresponding preconditioning methods 9. Block diagonal and Schur complement preconditionings 10. Estimates of eigenvalues and condition numbers for preconditional matrices 11. Conjugate gradient and Lanczos-type methods 12. Generalized conjugate gradient methods 13. The rate of convergence of the conjugate gradient method Appendices. 1. A Review of Some Required Concepts from Core Linear Algebra. 2. Floating Point Numbers and Errors in Computations. 3. Stability of Algorithms and Conditioning of Problems. 4. Numerically Effective Algorithms and Mathematical Software. 5. Some Useful Transformations in Numerical Linear Algebra and Their Applications. 6. Numerical Solutions of Linear Systems. 7. Least Squares Solutions to Linear Systems. 8. Numerical Matrix Eigenvalue Problems. 9. The Generalized Eigenvalue Problem. 10. The Singular Value Decomposition (SVD). 11. A Taste of Round-Off Error Analysis. Appendix A: A Brief Introduction to MATLAB. Appendix B: MATLAB and Selected MATLAB Programs. For numerical computation of the minimal Euclidean norm (least-squares) solution of overdetermined linear systems, usually direct solvers are used (like QR decomposition, see [4]). The iterative methods for such kind of problems need special assumptions about the system (consistency, full rank of the system matrix, some parameters they use or they give not the minimal length solution, [2,3,5,8,10,13]). In the present paper we purpose two iterative algorithms which generate sequences convergent to the minimal Euclidean length solution in the general case (inconsistent system and rank deficient matrix). The algorithms use only some combinations and properties of the well-known Kaczmarz iterative method ([13]) and need no special assumptions about the system. We present an iterative method for solving linear systems, which has the property of minimizing at every step the norm of the residual vector over a Krylov subspace. The algorithm is derived from t... 1. Overview of Operations Research. I. DETERMINISTIC MODELS. 2. Introduction to Linear Programming. 3. The Simplex Method. 4. Duality and Sensitivity Analysis. 5. Transportation Model and Its Variants. 6. Network Models. 7. Advanced Linear Programming. 8. Goal Programming. 9. Integer Linear Programming. 10. Deterministic Dynamic Programming. 11. Deterministic Inventory Models. II. PROBABILISTIC MODELS. 12. Review of Basic Probability. 13. Forecasting Models. 14. Decision Analysis and Games. 15. Probabilistic Dynamic Programming. 16. Probabilistic Inventory Models. 17. Queueing Systems. 18. Simulation Modeling. 19. Markovian Decision Process. III. NONLINEAR MODELS. 20. Classical Optimization Theory. 21. Nonlinear Programming Algorithms. Appendix A: Review of Matrix Algebra. Appendix B: Introduction to Simnet II. Appendix C: Tora and Simnet II Installation and Execution. Appendix D: Statistical Tables. Appendix E: Answers to Odd-Numbered Problems. Index. An iterative algorithm is given for solving a system Ax=k of n linear equations in n unknowns. The solution is given in n steps. It is shown that this method is a special case of a very general method which also includes Gaussian elimination. These general algorithms are essentially algorithms for finding an n dimensional ellipsoid. Connections are made with the theory of orthogonal polynomials and continued fractions. The algebraic reconstruction technique (ART), based on the well known algorithm proposed by Kaczmarz in 1937, is one of the most important class of solution methods for image reconstruction problems. But unfortunately, almost all the methods from the ART class give satisfactory results only in the case of consistent problems. In the inconsistent case (and unfortunately this is what happens in real applications, because of measurement errors) they give only more or less "controllable" versions of the exact solutions. This is exactly the case that we analyze in the present paper. We start with a theoretical analysis of the classical Kaczmarz's projection method in the case of an inconsistent linear least-squares problem and we prove that the approximations so obtained are at a certain distance from the set of exact least-squares solutions. This distance is controlled by the component of the right hand side of the problem lying in the orthogonal complement of the range of problem's matrix, i.e. exactly the component that makes the problem inconsistent. For overcoming this difficulty we consider an extended version of Kaczmarz's algorithm, previously analyzed by one of the authors. In the numerical experiments described in the last part of the paper we compare the above mentioned extension with two well known (ART) type algorithms for image reconstruction in two electromagnetic geotomography problems. The results indicate that the extended Kaczmarz algorithm gives much better results than the other two.