Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part II: Convergence theory

Summary In this paper we discuss bounds for the convergence rates of several domain decomposition algorithms to solve symmetric, indefinite linear systems arising from mixed finite element discretizations of elliptic problems. The algorithms include Schwarz methods and iterative refinement methods on locally refined grids. The implementation of Schwarz and iterative refinement algorithms have been discussed in part I. A discussion on the stability of mixed discretizations on locally refined grids is included and quantiative estimates for the convergence rates of some iterative refinement algorithms are also derived.Department of Mathematics, University of Wyoming, Laramie, WY 82071-3036. This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by NSF Grant ASC 9003002, while the author was a Visiting, Assistant Researcher at UCLA.     

The translation representation theorem

Short of a new theorem on semigroups of operators, a new proof of an old theorem on this subject is a suitable offering to Einar Hille on his 85th birthday.The work of both authors was supported in part by the National Science Foundation, the first author under Grant No. MCS-76-07039 and the second author under Grant No. MCS-77-04908 A 01.     

Local structure-preserving algorithms for partial differential equations

In this paper, we discuss the concept of local structure-preserving algorithms (SPAs) for partial differential equations, which are the natural generalization of the corresponding global SPAs. Local SPAs for the problems with proper boundary conditions are global SPAs, but the inverse is not necessarily valid. The concept of the local SPAs can explain the difference between different SPAs and provide a basic theory for analyzing and constructing high performance SPAs. Furthermore, it enlarges the applicable scopes of SPAs. We also discuss the application and the construction of local SPAs and derive several new SPAs for the nonlinear Klein-Gordon equation. This work was supported by the National Basic Research Program (Grant No. 2005CB321703). The first author was supported by the National Natural Science Foundation of China (Grant Nos. 40405019, 10471067) and the Major Research Projects of Jiangsu Province (Grant No. BK2006725); the second author was supported by the National Natural Science Foundation of China (Innovation Group) (Grant No. 40221503) and the third author was supported by the National Natural Science Foundation of China (Grant No. 10471145)     

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.     

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.     

Lower bounds for three-dimensional nonoverlapping domain decomposition algorithms

Summary. Lower bounds for the condition numbers of the preconditioned systems are obtained for the wire basket preconditioner and the Neumann-Neumann preconditioner in three dimensions. They show that the known upper bounds are sharp. Received January 28, 2001 / Revised version received September 3, 2001 / Published online January 30, 2002 This work was supported in part by the National Science Foundation under Grant Nos. DMS-9600133 and DMS-0074246     

Entropy of first return partitions of a Markov chain

Summary We consider the first return time distributions for each state in a Markov chain and show that finiteness of entropy of these distributions is a class property for recurrent and transient classes.The work of the second author was supported in part by National Science Foundation Grant GP 7631.     

Spectral conditioning and pseudospectral growth

Using the language of pseudospectra, we study the behavior of matrix eigenvalues under two scales of matrix perturbation. First, we relate Lidskii’s analysis of small perturbations to a recent result of Karow on the growth rate of pseudospectra. Then, considering larger perturbations, we follow recent work of Alam and Bora in characterizing the distance from a given matrix to the set of matrices with multiple eigenvalues in terms of the number of connected components of pseudospectra. J. V. Burke’s research was supported in part by National Science Foundation Grant DMS-0505712. A. S. Lewis’s research was supported in part by National Science Foundation Grant DMS-0504032. M. L. Overton’s research was supported in part by National Science Foundation Grant DMS-0412049.     

Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices

A real square matrix is said to be essentially non-negative if all of its off-diagonal entries are non-negative. We establish entrywise relative perturbation bounds for the exponential of an essentially non-negative matrix. Our bounds are sharp and contain a condition number that is intrinsic to the exponential function. As an application, we study sensitivity of continuous-time Markov chains. J. Xue was supported by the National Science Foundation of China under grant number 10571031, the Program for New Century Excellent Talents in Universities of China and Shanghai Pujiang Program. Q. Ye was supported in part by NSF under Grant DMS-0411502.     

Q-Learning Algorithms with Random Truncation Bounds and Applications to Effective Parallel Computing

Motivated by an important problem of load balancing in parallel computing, this paper examines a modified algorithm to enhance Q-learning methods, especially in asynchronous recursive procedures for self-adaptive load distribution at run-time. Unlike the existing projection method that utilizes a fixed region, our algorithm employs a sequence of growing truncation bounds to ensure the boundedness of the iterates. Convergence and rates of convergence of the proposed algorithm are established. This class of algorithms has broad applications in signal processing, learning, financial engineering, and other related fields. G. Yin’s research was supported in part by the National Science Foundation under Grants DMS-0603287 and DMS-0624849 and in part by the National Security Agency under Grant MSPF-068-029. C.Z. Xu’s research was supported in part by the National Science Foundation under Grants CCF-0611750, DMS-0624849, CNS-0702488, and CRI-0708232. L.Y. Wang’s research was supported in part by the National Science Foundation under Grants ECS-0329597 and DMS-0624849 and by the Michigan Economic Development Council.     

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 general parametric analysis approach and its implication to sensitivity analysis in interior point methods

Adler and Monteiro (1992) developed a parametric analysis approach that is naturally related to the geometry of the linear program. This approach is based on the availability of primal and dual optimal solutions satisfying strong complementarity. In this paper, we develop an alternative geometric approach for parametric analysis which does not require the strong complementarity condition. This parametric analysis approach is used to develop range and marginal analysis techniques which are suitable for interior point methods. Two approaches are developed, namely the LU factorization approach and the affine scaling approach. Presented at the ORSA/TIMS, Nashville, TN, USA, May 1991. Supported by the National Science Foundation (NSF) under Grant No. DDM-9109404 and Grant No. DMI-9496178. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at The University of Arizona. Supported in part by the GTE Laboratories and the National Science Foundation (NSF) under Grant No. CCR-9019469.     

Exploiting special structure in Karmarkar's linear programming algorithm

We propose methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems. We can use these constraints to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance. It is shown how various upper-bounding constraints can be handled implicitly in this way. Unfortunately, the situation for network constraints appears less favorable.Research supported in part by National Science Foundation Grant ECS-8602534, ONR Contract N00014-87-K-0212 and the US Army Research Office through the Mathematical Sciences Institute of Cornell University.     

Sublinear upper bounds for stochastic programs with recourse

Separable sublinear functions are used to provide upper bounds on the recourse function of a stochastic program. The resulting problem's objective involves the inf-convolution of convex functions. A dual of this problem is formulated to obtain an implementable procedure to calculate the bound. Function evaluations for the resulting convex program only require a small number of single integrations in contrast with previous upper bounds that require a number of function evaluations that grows exponentially in the number of random variables. The sublinear bound can often be used when other suggested upper bounds are intractable. Computational results indicate that the sublinear approximation provides good, efficient bounds on the stochastic program objective value.This research has been partially supported by the National Science Foundation. The first author's work was also supported in part by Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

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.     

Discrete weighted residual methods: A sensitive nonlinear boundary-value problem

The foundations, applications, and convergence properties of discrete weighted residual methods (DWRM's) are presented in Refs. 1–3. This paper serves to illustrate DWRM's for solving a sensitive nonlinear discrete boundary-value problem. The results indicate that DWRM's can be applied to provide models of increasing complexity which can then be utilized for the analysis and design of physical systems.The work of the first author was supported in part by the National Science Foundation, Grant No. GJ-1075. The work of the second author was supported by a Hertz Foundation Fellowship.     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

Competing symmetries,the logarithmic HLS inequality and Onofri's inequality ons n

The sharp version of the logarithmic Hardy-Littlewood-Sobolev inequality including the cases of equality is established. We then show that this implies Beckner's generalization of Onofri's inequality to arbitrary dimensions and determines the cases of equality.The work of the second author is partially supported by the U.S. National Science Foundation under Grant DMS-90-05729.     

A relaxation method for nonconvex quadratically constrained quadratic programs

We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

Additive Schwarz algorithms for parabolic convection-diffusion equations

Summary In this paper, we consider the solution of linear systems of algebraic equations that arise from parabolic finite element problems. We introduce three additive Schwarz type domain decomposition methods for general, not necessarily selfadjoint, linear, second order, parabolic partial differential equations and also study the convergence rates of these algorithms. The resulting preconditioned linear system of equations is solved by the generalized minimal residual method. Numerical results are also reported.This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003 at the Courant Institute, New York University and in part by the National Science Foundation under contract number DCR-8521451 and ECS-8957475 at Yale University