Multigrid Algorithms for the Solution of Linear Complementarity Problems Arising from Free Boundary Problems
Authors:
- Achi BrandtABAchi Brandt
- Colin W. CryerCCColin W. Cryer
- 1 December 1983
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 4 (4) , 655-684
Abstract
Several free boundary problems (including saturated-unsaturated flow through porous dams, elastic-plastic torsion and cavitating journal bearings) can be formulated as linear complementarity problems of the following type: Find a nonnegative function u which satisfies prescribed boundary conditions on a given domain and which, furthermore, satisfies a linear elliptic equation at each point of the domain where u is greater than zero. We show that the multigrid FAS algorithm, which was developed by Brandt to solve boundary value problems for elliptic partial differential equations, can easily be adapted to handle linear complementarity problems. For large problems, the resulting algorithm, PFAS (projected full approximation scheme) is significantly faster than previous single-grid algorithms, since the computation time is proportional to the number of grid points on the finest grid. We then introduce two further multigrid algorithms, PFASMD and PFMG. PFASMD is a modification of PFAS which is considerably faster than PFAS. Using PFMG (projected full multigrid) it is possible to solve a linear complementarity problem to within truncation error using less work than the equivalent of seven Gauss–Seidel sweeps on the finest grid.Keywords
This publication has 13 references indexed in Scilit:
- The solution of the axisymmetric elastic-plastic torsion of a shaft using varational inequalitiesJournal of Mathematical Analysis and Applications, 1980
- Multigrid Solutions to Elliptic Flow Problems1979
- Complementarity and Fixed Point Problems1978
- On the solution of large, structured linear complementarity problems: The block partitioned caseApplied Mathematics & Optimization, 1977
- Multi-level adaptive solutions to boundary-value problemsMathematics of Computation, 1977
- On the solution of large, structured linear complementarity problems: The tridiagonal caseApplied Mathematics & Optimization, 1976
- A finite element approximation of a variational inequality related to hydraulicsCalcolo, 1976
- On a problem of the theory of lubrication governed by a variational inequalityApplied Mathematics & Optimization, 1976
- The Solution of a Quadratic Programming Problem Using Systematic OverrelaxationSIAM Journal on Control, 1971
- The method of Christopherson for solving free boundary problems for infinite journal bearings by means of finite differencesMathematics of Computation, 1971