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.
Most of the direct methods for soft constraint problems are least-squares methods such as LU-decompos -ition and QR-decompo -sition @cite_30 . The UI layout solver HiRise @cite_33 is an example of this category. HiRise2 @cite_22 is an extended version of the HiRise constraint solver which solves hierarchies of linear constraints by applying an LU-decompos -ition-based simplex method.
@cite_30 @cite_22 @cite_33
2157057346 1993924106
In this paper, we propose a constrained least squares approach for stably computing Laplacian deformation with strict positional constraints. In the existing work on Laplacian deformation, strict positional constraints are described using large values of least squares weights, which often cause numerical problems when Laplacians are described using cotangent weights. In our method, we describe strict positional constraints as hard constraints. We solve the combination of hard and soft constraints by constructing a typical least squares matrix form using QR decomposition. In addition, our method can manage shape deformation under over-constraints, such as redundant and conflicting constraints. Our framework achieves excellent performance for interactive deformation of mesh models. We propose a scalable algorithm called HiRise2 for incrementally solving soft linear constraints over real domains. It is based on a framework for soft constraints, known as constraint hierarchies, to allow effective modeling of user interface applications by using hierarchical preferences for constraints. HiRise2 introduces LU decompositions to improve the scalability of an incremental simplex method. Using this algorithm, we implemented a constraint solver. We also show the results of experiments on the performance of the solver.