High-order adaptive finite element-singly implicit Runge-Kutta methods for parabolic differential equations

We describe an adaptive mesh refinement finite element method-of-lines procedure for solving one-dimensional parabolic partial differential equations. Solutions are calculated using Galerkin's method with a piecewise hierarchical polynomial basis in space and singly implicit Runge-Kutta (SIRK) methods in time. A modified SIRK formulation eliminates a linear systems solution that is required by the traditional SIRK formulation and leads to a new reduced-order interpolation formula. Stability and temporal error estimation techniques allow acceptance of approximate solutions at intermediate stages, yielding increased efficiency when solving partial differential equations. A priori energy estimates of the local discretization error are obtained for a nonlinear scalar problem. A posteriori estimates of local spatial discretization errors, obtained by order variation, are used with the a priori error estimates to control the adaptive mesh refinement strategy. Computational results suggest convergence of the a posteriori error estimate to the exact discretization error and verify the utility of the adaptive technique.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-90-0194; the U.S. Army Research Office under Contract Number DAAL 03-91-G-0215; by the National Science Foundation under Grant Number CDA-8805910; and by a grant from the Committee on Research, Tulane University.     

On the convergence of the conjugate gradient method for singular capacitance matrix equations from the Neumann problem of the Poisson equation

Summary It is shown analytically in this work that the conjugate gradient method is an efficient means of solving the singular capacitance matrix equations arising from the Neumann problem of the Poisson equation. The total operation count of the algorithm does not exceed constant timesN ²logN(N=1/h) for any bounded domain with sufficiently smooth boundary.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385. Also partially supported by the Energy Research and Development Administration     

The solution of the two-dimensional sine-Gordon equation using the method of lines

The method of lines is used to transform the initial/boundary-value problem associated with the two-dimensional sine-Gordon equation in two space variables into a second-order initial-value problem. The finite-difference methods are developed by replacing the matrix-exponential term in a recurrence relation with rational approximants. The resulting finite-difference methods are analyzed for local truncation error, stability and convergence. To avoid solving the nonlinear system a predictor–corrector scheme using the explicit method as predictor and the implicit as corrector is applied. Numerical solutions for cases involving the most known from the bibliography line and ring solitons are given.     

Truncation error analysis by means of approximant systems and inclusion regions

Summary A general approach to truncation error analysis is described, in which bounds for the truncation error are determined by means of inclusion regions, and the notion of bestness is meaningfully formulated. A new mathematical structure (approximant system) is introduced and developed. It consists of a family of infinite processes having a natural structure for truncation error analysis. Applications of the methods are included for infinite series, Cesaro sums, approximate integration, an iterative method for solving equations, Padé approximants and continued fractions.Research supported in part by the National Science Foundation under Grant No. MPS 74-22111 and by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-70-1888. The United States Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon     

IMPLICIT-EXPLICIT RUNGE-KUTTA-ROSENBROCK METHODS WITH ERROR ANALYSIS FOR NONLINEAR STIFF DIFFERENTIAL EQUATIONS

Implicit-explicit Runge-Kutta-Rosenbrock methods are proposed to solve nonlinear stiff ordinary differential equations by combining linearly implicit Rosenbrock methods with ex-plicit Runge-Kutta methods.First,the general order conditions up to order 3 are obtained.Then,for the nonlinear stiff initial-value problems satisfying the one-sided Lipschitz condi-tion and a class of singularly perturbed initial-value problems,the corresponding errors of the implicit-explicit methods are analysed.At last,some numerical examples are given to verify the validity of the obtained theoretical results and the effectiveness of the methods.     

QPCOMP: A quadratic programming based solver for mixed complementarity problems

QPCOMP is an extremely robust algorithm for solving mixed nonlinear complementarity problems that has fast local convergence behavior. Based in part on the NE/SQP method of Pang and Gabriel [14], this algorithm represents a significant advance in robustness at no cost in efficiency. In particular, the algorithm is shown to solve any solvable Lipschitz continuous, continuously differentiable, pseudo-monotone mixed nonlinear complementarity problem. QPCOMP also extends the NE/SQP method for the nonlinear complementarity problem to the more general mixed nonlinear complementarity problem. Computational results are provided, which demonstrate the effectiveness of the algorithm. This material is based on research supported by National Science Foundation Grant CCR-9157632, Department of Energy Grant DE-FG03-94ER61915, and the Air Force Office of Scientific Research Grant F49620-94-1-0036.     

Truncated-newtono algorithms for large-scale unconstrained optimization

We present an algorithm for large-scale unconstrained optimization based onNewton's method. In large-scale optimization, solving the Newton equations at each iteration can be expensive and may not be justified when far from a solution. Instead, an inaccurate solution to the Newton equations is computed using a conjugate gradient method. The resulting algorithm is shown to have strong convergence properties and has the unusual feature that the asymptotic convergence rate is a user specified parameter which can be set to anything between linear and quadratic convergence. Some numerical results on a 916 vriable test problem are given. Finally, we contrast the computational behavior of our algorithm with Newton's method and that of a nonlinear conjugate gradient algorithm. This research was supported in part by DOT Grant CT-06-0011, NSF Grant ENG-78-21615 and grants from the Norwegian Research Council for Sciences and the Humanities and the Norway-American Association. This paper was originally presented at the TIMS-ORSA Joint National Meeting, Washington, DC, May 1980.     

Relation between the memory gradient method and the Fletcher-Reeves method

The minimization of a function of unconstrained variables is considered using the memory gradient method. It is shown that, for the particular case of a quadratic function, the memory gradient algorithm and the Fletcher-Reeves algorithm are identical.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67. In more expanded form, it can be found in Ref. 1.     

Central difference schemes and stiff boundary value problems

Consider the two-point boundary value problem for a stiff system of ordinary differential equations without turning points. Conditions are derived such that the solutions of centered implicit Runge-Kutta methods converge to the solution of the differential equations.Dedicated to Germund Dahlquist, on the occasion of his 60th birthday.This work was supported by the National Science Foundation under Grant No. DMS-8312264 and by the Office of Naval Research under contract No. NOOO14-83-K-0422.     

Finite-termination schemes for solving semi-infinite satisfycing problems

The problem of finding a parameter which satisfies a set of specifications in inequality form is sometimes referred to as the satisfycing problem. We present a family of methods for solving, in a finite number of iterations, satisfycing problems stated in the form of semi-infinite inequalities. These methods range from adaptive uniform discretization methods to outer approximation methods.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-8713334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, and the State of California MICRO Program Grant 532410-19900.     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.     

Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs

A parallel successive overrelaxation (SOR) method is proposed for the solution of the fundamental symmetric linear complementarity problem. Convergence is established under a relaxation factor which approaches the classical value of 2 for a loosely coupled problem. The parallel SOR approach is then applied to solve the symmetric linear complementarity problem associated with the least norm solution of a linear program.This work was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Science Foundation Grant DCR-84-20963 and Air Force Office of Scientific Research Grants AFOSR-ISSA-85-00080 and AFOSR-86-0172.on leave from CRAI, Rende, Cosenza, Italy.     

A transformation technique for optimal control problems with partially linear state inequality constraints

This paper considers optimal control problems involving the minimization of a functional subject to differential constraints, terminal constraints, and a state inequality constraint. The state inequality constraint is of a special type, namely, it is linear in some or all of the components of the state vector.A transformation technique is introduced, by means of which the inequality-constrained problem is converted into an equality-constrained problem involving differential constraints, terminal constraints, and a control equality constraint. The transformation technique takes advantage of the partial linearity of the state inequality constraint so as to yield a transformed problem characterized by a new state vector of minimal size. This concept is important computationally, in that the computer time per iteration increases with the square of the dimension of the state vector.In order to illustrate the advantages of the new transformation technique, several numerical examples are solved by means of the sequential gradient-restoration algorithm for optimal control problems involving nondifferential constraints. The examples show the substantial savings in computer time for convergence, which are associated with the new transformation technique.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075, and by the National Science Foundation, Grant No. MCS-76-21657.     

More results on the convergence of iterative methods for the symmetric linear complementarity problem

In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin.     

A note on an open problem in linear complementarity

LetK be the class ofn × n matricesM such that for everyn-vectorq for which the linear complementarity problem (q, M) is feasible, then the problem (q, M) has a solution. Recently, a characterization ofK has been obtained by Mangasarian [5] in his study of solving linear complementarity problems as linear programs. This note proves a result which improves on such a characterization.Research sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385.     

Affine systems inL 2 (ℝ d ) II: Dual systems

The fiberization of affine systems via dual Gramian techniques, which was developed in previous papers of the authors, is applied here for the study of affine frames that have an affine dual system. Gramian techniques are also used to verify whether a dual pair of affine frames is also a pair of bi-orthogonal Riesz bases. A general method for a painless derivation of a dual pair of affine frames from an arbitrary MRA is obtained via the mixed extension principle. This work was partially sponsored by the National Science Foundation under Grants DMS-9102857, DMS-9224748, and DMS-9626319, by the United States Army Research Office under Contracts DAAL03-G-90-0090, DAAH04-95-1-0089, and by the Strategic Wavelet Program Grant from the National University of Singapore.     

An Inexact Newton Method Derived from Efficiency Analysis

We consider solving an unconstrained optimization problem by Newton-PCG like methods in which the preconditioned conjugate gradient method is applied to solve the Newton equations. The main question to be investigated is how efficient Newton-PCG like methods can be from theoretical point of view. An algorithmic model with several parameters is established. Furthermore, a lower bound of the efficiency measure of the algorithmic model is derived as a function of the parameters. By maximizing this lower bound function, the parameters are specified and therefore an implementable algorithm is obtained. The efficiency of the implementable algorithm is compared with Newtons method by theoretical analysis and numerical experiments. The results show that this algorithm is competitive.Mathematics Subject Classification: 90C30, 65K05.This work was supported by the National Science Foundation of China Grant No. 10371131, and Hong Kong Competitive Earmarked Research Grant CityU 1066/00P from Hong Kong University Grant Council     

A smoothing projected Newton-type algorithm for semi-infinite programming

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

ADAPTIVITY IN SPACE AND TIME FOR MAGNETOQUASISTATICS

This paper addresses fully space-time adaptive magnetic field computations. We describe an adaptive Whitney finite element method for solving the magnetoquasistatic formulation of Maxwell＇s equations on unstructured 3D tetrahedral grids. Spatial mesh re- finement and coarsening are based on hierarchical error estimators especially designed for combining tetrahedral H（curl）-conforming edge elements in space with linearly implicit Rosenbrock methods in time. An embedding technique is applied to get efficiency in time through variable time steps. Finally, we present numerical results for the magnetic recording write head benchmark problem proposed by the Storage Research Consortium in Japan.     

Solution of the least squares method problem of pairwise comparison matrices

The aim of the paper is to present a new global optimization method for determining all the optima of the Least Squares Method (LSM) problem of pairwise comparison matrices. Such matrices are used, e.g., in the Analytic Hierarchy Process (AHP). Unlike some other distance minimizing methods, LSM is usually hard to solve because of the corresponding nonlinear and non-convex objective function. It is found that the optimization problem can be reduced to solve a system of polynomial equations. Homotopy method is applied which is an efficient technique for solving nonlinear systems. The paper ends by two numerical example having multiple global and local minima. This research was supported in part by the Hungarian Scientific Research Fund, Grant No. OTKA K 60480.