Co-volume methods for degenerate parabolic problems

Summary A complementary volume (co-volume) technique is used to develop a physically appealing algorithm for the solution of degenerate parabolic problems, such as the Stefan problem. It is shown that, these algorithms give rise to a discrete semigroup theory that parallels the continuous problem. In particular, the discrete Stefan problem gives rise to nonlinear semigroups in both the discreteL ¹ andH ^–1 spaces.The first author was supported by a grant from the Hughes foundation, and the second author was supported by the National Science Foundation Grant No. DMS-9002768 while this work was undertaken. This work was supported by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

A nonconforming finite element method for a two-dimensional curl–curl and grad-div problem

A numerical method for a two-dimensional curl–curl and grad-div problem is studied in this paper. It is based on a discretization using weakly continuous P ₁ vector fields and includes two consistency terms involving the jumps of the vector fields across element boundaries. Optimal convergence rates (up to an arbitrary positive ) in both the energy norm and the L ₂ norm are established on graded meshes. The theoretical results are confirmed by numerical experiments. The work of the first author was supported in part by the National Science Foundation under Grant No. DMS-03-11790 and by the Humboldt Foundation through her Humboldt Research Award. The work of the third author was supported in part by the National Science Foundation under Grant No. DMS-06-52481.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

Mean convergence of hermite interpolation revisited

The first author is supported by the Hungarian National Foundation for Scientific Research Grant No. 1910 and No. T7570, and the second author is supported by the National Science Foundation Grant No. 9302721. The work was done during the first author's visit in Eugene, Oregon in 1993, and was completed during the second author's visit to the Mathematisches Institut, University of Erlange-Nürnberg, supported by the Alexander von Humboldt Foundation.     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.     

Structural properties of inner amenable groups

For infinite discrete groups, Effros introduced the notion of inner amenability which gives a new classification of discrete groups. The inner amenability is a considerably weaker condition than amenability, but closely related to the quite deep property Γ of groups. In this paper the author investigates the structures of inner amenable groups by theoretical set theory. A sequence of characterizations of inner amenable groups is given here by developing the well-known Folner's conditions for amenable locally compact groups. This work is partly supported by the National Science Foundation of China.     

An LP-based successive overrelaxation method for linear complementarity problems

A sparsity preserving LP-based SOR method for solving classes of linear complementarity problems including the case where the given matrix is positive-semidefinite is proposed. The LP subproblems need be solved only approximately by a SOR method. Heuristic enhancement is discussed. Numerical results for a special class of problems are presented, which show that the heuristic enhancement is very effective and the resulting program can solve problems of more than 100 variables in a few seconds even on a personal computer.This research was sponsored by the Air Force Office of Scientific Research, Grant No. AFOSR-86-0124. Part of this material is based on work supported by the National Science Foundation under Grant No. MCS-82-00632.The author is grateful to Dr. R. De Leone for his helpful and constructive comments on this paper.     

Fourier spectral approximation to long-time behavior of three dimensional Ginzburg-Landau type equation*

In this paper, we consider a three dimensional Ginzburg–Landau type equation with a periodic initial value condition. A fully discrete Galerkin–Fourier spectral approximation scheme is constructed, and then the dynamical properties of the discrete system are analyzed. First, the existence and convergence of global attractors of the discrete system are proved by a priori estimates and error estimates of the discrete solution, and the numerical stability and convergence of the discrete scheme are proved. Furthermore, the long-time convergence and stability of the discrete scheme are proved. *This work was supported by the National Natural Science Foundation of China (No.: 10432010 and 10571010)     

On the formulation and theory of the Newton interior-point method for nonlinear programming

In this work, we first study in detail the formulation of the primal-dual interior-point method for linear programming. We show that, contrary to popular belief, it cannot be viewed as a damped Newton method applied to the Karush-Kuhn-Tucker conditions for the logarithmic barrier function problem. Next, we extend the formulation to general nonlinear programming, and then validate this extension by demonstrating that this algorithm can be implemented so that it is locally and Q-quadratically convergent under only the standard Newton method assumptions. We also establish a global convergence theory for this algorithm and include promising numerical experimentation.The first two authors were supported in part by NSF Cooperative Agreement No. CCR-8809615, by Grants AFOSR 89-0363, DOE DEFG05-86ER25017, ARO 9DAAL03-90-G-0093, and the REDI Foundation. The fourth author was supported in part by NSF DMS-9102761 and DOE DE-FG02-93ER25171. The authors would like to thank Sandra Santos for painstakingly proofreading an earlier verion of this paper.     

General linear methods with external stages of different orders

The approach introduced recently by Albrecht to derive order conditions for Runge-Kutta formulas based on the theory of A-methods is also very powerful for the general linear methods. In this paper, using Albrecht's approach, we formulate the general theory of order conditions for a class of general linear methods where the components of the propagating vector of approximations to the solution have different orders. Using this theory we derive a class of diagonally implicit multistage integration methods (DIMSIMs) for which the global order is equal to the local order. We also derive a class of general linear methods with two nodal approximations of different orders which facilitate local error estimation. Our theory also applies to the class of two-step Runge-Kutta introduced recently by Jackiewicz and Tracogna.The work of the first author was supported by the National Science Foundation under grant NSF DMS-9208048. The work of the second author was supported by the Italian Consiglio Nazionale delle Richerche.     

Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes

We give several additive Schwarz domain decomposition methods for solving finite element problems which arise from the discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Our theory requires no assumption (for the main results) on the substructures which constitute the whole domain, so each substructure can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved and both the coarse meshes and the fine meshes need not be quasi-uniform. In this general setting, our algorithms have the same optimal convergence rate of the usual domain decomposition methods on structured meshes. The condition numbers of the preconditioned systems depend only on the (possibly small) overlap of the substructures and the size of the coares grid, but is independent of the sizes of the subdomains.Revised version on Sept. 20, 1994. Original version: CAM Report 93-40, Dec. 1993, Dept. of Math., UCLA.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and ONR under contract ONR-N00014-92-J-1890.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and subcontract DAAL03-91-C-0047.     

Tychonoff property for linear groups

A criterion for a wide class of topological groups which includes linear discrete groups and Lie groups to be Tychonoff groups is established. The main result provides a criterion for an almost polycyclic group to have the Tychonoff property. By the well-known Tits alternative, this yields the required criterion for linear discrete groups. In conclusion it is pointed out that a particular case of the presented proof yields a Tychonoff property criterion for Lie groups. In addition, an example of a polycyclic group without Tychonoff subgroups of finite index is constructed. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 269–279, February, 1998. The author wishes to express his gratitude to R. I. Grigorchuk for setting the problem and his interest in the work. This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00182 and by the American Mathematical Society Fund.     

Convex Optimization Approach to Dynamic Output Feedback Control for Delay Differential Systems of Neutral Type

In this paper, the design problem of the dynamic output feedback controller for the asymptotic stabilization of a class of linear delay differential systems of the neutral type is considered. A criterion for the existence of such controller is derived based on the matrix inequality approach combined with the Lyapunov method. A parametrized characterization of the controller is given in terms of the feasible solutions to certain matrix inequalities, which can be solved by various convex optimization algorithms. A numerical example is given to illustrate the proposed design method. This work was supported by Grant R05-2003-000-10173-0 from the Korea Science and Engineering Foundation. The author is grateful to J. S. Park and C. J. Cho for valuable support.     

Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem

Necessary and sufficient conditions are established for the convergence of various iterative methods for solving the linear complementarity problem. The fundamental tool used is the classical notion of matrix splitting in numerical analysis. The results derived are similar to some well-known theorems on the convergence of iterative methods for square systems of linear equations. An application of the results to a strictly convex quadratic program is also given.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571.The author gratefully acknowledges several comments by K. Truemper on the topics of this paper.     

Nonobtuse Tetrahedral Partitions that Refine Locally Towards Fichera-Like Corners

Linear tetrahedral finite elements whose dihedral angles are all nonobtuse guarantee the validity of the discrete maximum principle for a wide class of second order elliptic and parabolic problems. In this paper we present an algorithm which generates nonobtuse face-to-face tetrahedral partitions that refine locally towards a given Fichera-like corner of a particular polyhedral domain. The first author was supported by the Swedish Foundation for Strategic Research, the second author was supported by Grant No. 49051 of the Academy of Finland, the third author was supported by Grant No. A 1019201 of the Academy of Sciences of the Czech Republic and by Institutional Research Plan AV0Z 10190503.     

On the method of complementary functions for nonlinear boundary-value problems

We show that, like the method of adjoints, the method of complementary functions can be effectively used to solve nonlinear boundary-value problems.This work was supported by the Alexander von Humboldt Foundation. The author is thankful to Prof. G. Hämmerlin for providing the facilities and to Miss J. Gumberger for performing numerical tests. The author is also indebted to Dr. S. M. Roberts for his suggestions on the first draft of this paper.     

Identifying an optimal basis in linear programming

We propose a sufficient condition that allows an optimal basis to be identified from a central path point in a linear programming problem. This condition can be applied when there is a gap in the sorted list of slack values. Unlike previously known conditions, this condition is valid for real-number data and does not involve the number of bits in the data.This work is supported in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF Grant DMS-8920550. Also supported in part by an NSF Presidential Young Investigator Award with matching funds received from AT&T and the Xerox Corporation. Part of this work was carried out while the author was visiting the Sandia National Laboratories, supported by the U.S. Department of Energy under Contract DE-AC04-76DP00789.The author is supported in part by NSF Grant DDM-9207347. Part of this work was carried out while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and the IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Strongest postcondition semantics as the formal basis for reverse engineering

Reverse engineering of program code is the process of constructing a higher level abstraction of an implementation in order to facilitate the understanding of a system that may be in a “legacy” or “geriatric” state. Changing architectures and improvements in programming methods, including formal methods in software development and object-oriented programming, have prompted a need to reverse engineer and re-engineer program code. This paper describes the application of the strongest postcondition predicate transformer (sp) as the formal basis for the reverse engineering of imperative program code. This work is supported in part by the National Science Foundation grants CCR-9407318, CCR-9209873, and CDA-9312389. This author is supported in part by a NASA Graduate Student Researchers Program Fellowship.     

Aperiodic tilings of the hyperbolic plane by convex polygons

Several aperiodic hyperbolic tiling systems consisting of a single convex tile are constructed. Research partially supported by GIF grant no. G-454.213.06.95 and SFB 343 Bielefeld. The work of the first author was supported in part by NSF grant DMS-9424613. The work of the second author was supported in part by a grant of the Israel Academy of Sciences, and by the Edmund Landau Center for Research in Mathematical Analysis supported by the Minerva Foundation (Federal Republic of Germany).