Minkowski matrices.

C. W. Cryer · ACM Transactions on Mathematical Software · 1983

Many free boundary problems in mechanics and physics can be approximated by a linear complementarity problem given an n × n matrix M and q E R n find w, z ~ R" such that w=Mz+q>_O, z~O,In analogy with alternating direction methods for fimte difference equations, problem (*) may often be solved iteratively by solving a sequence of "one-dimensional" linear complementarity problems for which M is a trldiagonal Mmkowskl matrix (M has positive principal minors, positive diagonal elements, and nonposltive off-diagonal elements).An efficient algorithm is developed for the solution of linear complementarity problems for tridiagonal Minkowski matrices.The new algorithm is a modification of Saigal's algorithm, the most important change being that the data are scanned in alternating forward and backward passes.The new algorithm is significantly faster than previous algorithms, as is shown both theoretically and by considenng two test problems introduced by Cottle and Sacher Categories and SubJect Descriptors.G 1 6 [Numerical Analysis] Optimization; G.4 [ M a t h e m a t i c s of Computing].Mathematical Software, J.2 [ C o m p u t e r Applications].Physical Sciences and Engineering

Cited by 25 works. doi:10.1145/357456.2181 Open-access PDF

References