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

article Free Access Share on The efficient solution of linear complementarity problems for tridiagonal Minkowski matrices Author: C. W. Cryer Institut fur Numerische und Instrumentelle Mathematik, Westfalische Wilhelms-Universitat, Emstemstrasse 62, D-4400 Munster, West Germany Institut fur Numerische und Instrumentelle Mathematik, Westfalische Wilhelms-Universitat, Emstemstrasse 62, D-4400 Munster, West GermanyView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 9Issue 2June 1983 pp 199–214https://doi.org/10.1145/357456.357459Published:01 June 1983Publication History 6citation516DownloadsMetricsTotal Citations6Total Downloads516Last 12 Months31Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

When the method of finite differences is used to approximately solve a boundary value problem for an elliptic partial differential equation over a two-dimensional domain (R with boundary 0(R, the first step is to choose a set of net-points 9Z.Next, a system of algebraic equations connecting the values of the approximate solutions at the net-points is set up.Finally, the system of algebraic equations is solved.Usually, i)Z is taken to be the set of points belonging to a rectangular grid, together with the points of intersection of grid-lines with 0(R.When a computer is used, one or more of the following assumptions are often made in order to simplify the programming: (1) All the points of OZ are grid-points; (2) the "interior net-points" are "grid-connected"; (3) the number of "irregular" net-points is much smaller than the number of "regular" net-points.In the present paper these three assumptions are analyzed.

Two algorithms for solving free boundary problems in two dimensions are described. The algorithms use the method of finite differences and are automated versions of methods due to Southwell. The algorithms have been implemented as a general program FREEBOUN, and the numerical results that were obtained using this program are discussed.

A boundary value problem for the quasi-linear elliptic equation ( x x / q 2 s ) x + ( x y / q 2 s ) y = 0, where q 2 = x x 2 + x y 2 , 0 ≤ s < 1/2, is solved numerically, and the numerical process is analyzed mathematically.