Parallel interval multisplittings

Summary We introduce interval multisplittings to enclose the setS={A^–1b|A[A], b[b]}, where [A] denotes an interval matrix and [b] an interval vector. The resulting iterative multisplitting methods have a natural parallelism. We investigate these methods with respect to convergence, speed of convergence and quality of the resulting enclosure forS.Dedicated to the memory of Peter Henrici     

Performance of ILU factorization preconditioners based on multisplittings

Summary. In this paper, we study the convergence of multisplitting methods associated with a multisplitting which is obtained from the ILU factorizations of a general H-matrix, and then we propose parallelizable ILU factorization preconditioners based on multisplittings for a block-tridiagonal H-matrix. We also describe a parallelization of preconditioned Krylov subspace methods with the ILU preconditioners based on multisplittings on distributed memory computers such as the Cray T3E. Lastly, parallel performance results of the preconditioned BiCGSTAB are provided to evaluate the efficiency of the ILU preconditioners based on multisplittings on the Cray T3E. Mathematics Subject Classification (2000):65F10, 65Y05, 65F50This work was supported by Korea Research Foundation Grant (KRF-2001-015-DP0051)     

Solution manifolds and submanifolds of parametrized equations and their discretization errors

Summary The paper concerns solution manifolds of nonlinear parameterdependent equations (1)F(u, )=y₀ involving a Fredholm operatorF between (infinite-dimensional) Banach spacesX=Z× andY, and a finitedimensional parameter space . Differntial-geometric ideas are used to discuss the connection between augmented equations and certain onedimensional submanifolds produced by numerical path-tracing procedures. Then, for arbitrary (finite) dimension of , estimates of the error between the solution manifold of (1) and its discretizations are developed. These estimates are shown to be applicable to rather general nonlinear boundaryvalue problems for partial differential equations.This work was in part supported by the U.S. Air Force Office of Scientific Research under Grant 80-0176, the National Science Foundation under Grant MCS-78-05299, and the Office of Naval Research under Contract N-00014-80-C-0455     

Finite element solution of nonlinear elliptic problems

Summary The study of the finite element approximation to nonlinear second order elliptic boundary value problems with mixed Dirichlet-Neumann boundary conditions is presented. In the discretization variational crimes are commited (approximation of the given domain by a polygonal one, numerical integration). With the assumption that the corresponding operator is strongly monotone and Lipschitz-continuous and that the exact solutionuH ¹(), the convergence of the method is proved; under the additional assumptionuH ²(), the rate of convergenceO(h) is derived without the use of Green's theorem.     

On fully discrete Galerkin methods of second-order temporal accuracy for the nonlinear Schrödinger equation

Summary We approximate the solutions of an initial- and boundary-value problem for nonlinear Schrödinger equations (with emphasis on the cubic nonlinearity) by two fully discrete finite element schemes based on the standard Galerkin method in space and two implicit. Crank-Nicolson-type second-order accurate temporal discretizations. For both schemes we study the existence and uniqueness of their solutions and proveL ² error bounds of optimal order of accuracy. For one of the schemes we also analyze one step of Newton's method for solving the nonlinear systems that arise at every time step. We then implement this scheme using an iterative modification of Newton's method that, at each time stept ⁿ , requires solving a number of sparse complex linear systems with a matrix that does not change withn. The effect of this inner iteration is studied theoretically and numerically.The work of these authors was supported by the Institute of Applied and Computational Mathematics of the Research Center of Crete-FORTH and the Science Alliance program of the University of TennesseeThe work of this author was supported by the AFOSR Grant 88-0019     

Monotonicity and boundedness in implicit Runge-Kutta methods

Summary This paper concerns the analysis of implicit Runge-Kutta methods for approximating the solutions to stiff initial value problems. The analysis includes the case of (nonlinear) systems of differential equations that are essentially more general than the classical test equationU=U (with a complex constant). The properties of monotonicity and boundedness of a method refer to specific moderate rates of growth of the approximations during the numerical calculations. This paper provides necessary conditions for these properties by using the important concept of algebraic stability (introduced by Burrage, Butcher and by Crouzeix). These properties will also be related to the concept of contractivity (B-stability) and to a weakened version of contractivity.     

Mixed finite elements in ℝ3

Summary We present here some new families of non conforming finite elements in ³. These two families of finite elements, built on tetrahedrons or on cubes are respectively conforming in the spacesH(curl) andH(div). We give some applications of these elements for the approximation of Maxwell's equations and equations of elasticity.First, we introduce some notations K is a tetrahedron or a cube, thevolume of which is - K is its boundary - f is a face ofK, thesurface of which is - a is an edge, the length of which is - L ² (K) is the usual Hilbert space of square integrable functions defined onK - H ^m (K) {L ²(K); L ²(K); ||m}, where =(₁, ₂, ₃) is a multi-index; ||=₁+₂+₃ - curlu u, (defined by using the distributional derivative) foru=(u ₁,u ₂,u ₃);u _iL ² (K) - H(curl) {u(L ² (K))³; curlu(L ² (K)) ³} - divu ·u - H(div) {u(L ² (K)) ³; divuL ² (K)} - D ^k u is thek-th differential operator associated tou, which is a (k+1)-multilinear operator acting on ³ - k is an index - _k is the linear space of polynomials, the degree of which is less or equal tok - _k is the group of all permutations of the set {1, 2, ...,k} - c orc will stand for any constant depending possibly on      

Compactness method in the finite element theory of nonlinear elliptic problems

Summary Finite element approximation of a nonlinear elliptic pseudomonotone second-order boundary value problem in a bounded nonpolygonal domain with mixed Dirichlet-Neumann boundary conditions is studied. In the discretization we approximate the domain by a polygonal one, use linear conforming triangular elements and evaluate integrals by numerical quadratures. We prove the solvability of the discrete problem and on the basis of compactness properties of the corresponding operator (which is not monotone in general) we prove the convergence of approximate solutions to an exact weak solutionuH ¹ ). No additional assumption on the regularity of the exact solution is needed.     

The finite element method for nonlinear elliptic equations with discontinuous coefficients

Summary The study of the finite element approximation to nonlinear second order elliptic boundary value problems with discontinuous coefficients is presented in the case of mixed Dirichlet-Neumann boundary conditions. The change in domain and numerical integration are taken into account. With the assumptions which guarantee that the corresponding operator is strongly monotone and Lipschitz-continuous the following convergence results are proved: 1. the rate of convergenceO(h ) if the exact solutionuH ¹ () is piecewise of classH ¹⁺ (0<1);2. the convergence without any rate of convergence ifuH ¹ () only.     

On the convergence of multistep methods for nonlinear stiff differential equations

Summary Convergence estimates are given forA()-stable multistep methods applied to singularly perturbed differential equations and nonlinear parabolic problems. The approach taken here combines perturbation arguments with frequency domain techniques.     

Asymptotic near optimality of the bisection method

Summary We seek a approximation to a zero of an infinitely differentiable functionf: [0, 1] such thatf(0)0 andf(1)0. It is known that the error of the bisection method usingn function evaluations is 2^–(n+1). If the information used are function values, then it is known that bisection information and the bisection algorithm are optimal. Traub and Woniakowski conjectured in [5] that the bisection information and algorithm are optimal even if far more general information is permitted. They permit adaptive (sequential) evaluations of arbitrary linear functionals and arbitrary transformations of this information as algorithms. This conjecture was established in [2]. That is forn fixed, the bisection information and algorithm are optimal in the worst case setting. Thus nothing is lost by restricting oneself to function values.One may then ask whether bisection is nearly optimal in theasymptotic worst case sense, that is,possesses asymptotically nearly the best rate of convergence. Methods converging fast asymptotically, like Newton or secant type, are of course, widely used in scientific computation. We prove that the answer to this question is positive for the classF of functions having zeros ofinfinite multiplicity and information consisting of evaluations of continuous linear functionals. Assuming that everyf inF has zeroes withbounded multiplicity, there are known hybrid methods which have at least quadratic rate of convergence asn tends to infinity, see e.g., Brent [1], Traub [4] and Sect. 1.     

Superlinear convergence of symmetric Huang's class of methods

Summary In this paper the problem of minimizing the functionalf:DR ⁿ R is considered. Typical assumptions onf are assumed. A class of Quasi-Newton methods, namely Huang's class of methods is used for finding an optimal solution of this problem. A new theorem connected with this class is presented. By means of this theorem some convergence results known up till now only for the methods which satisfy Quasi-Newton condition are extended, that is the results of superlinear convergence of variable metric methods in the cases of exact and asymptotically exact minimization and the so-called direct-prediction case. This theorem allows to interpretate one of the parameters as the scaling parameter.     

Zur Lösung parameterabhängiger nichtlinearer Gleichungen mit singulären Jacobi-Matrizen

Summary For solving the nonlinear systemG(x, t)=0,G| ⁿ × ^{1 n} , which is assumed to have a smooth curve of solutions a continuation method with self-choosing stepsize is proposed. It is based on a PC-principle using an Euler-Cauchy-predictor and Newton's iteration as corrector. Under the assumption thatG is sufficiently smooth and the total derivative (₁ G(x, t)₂ G(x, t)) has full rankn along the method is proven to terminate with a solution (x ^N , 1) of the system fort=1. It works succesfully, too, if the Jacobians ₁ G(x, t) become singular at some points of , e.g., if has turning points. The method is especially able to give a point-wise approximation of the curve implicitly defined as solution of the system mentioned above.

     

A comparison result for multisplittings and waveform relaxation methods

We show that certain multisplitting iterative methods based on overlapping blocks yield faster convergence than corresponding nonoverlapping block iterations, provided the coefficient matrix is an M-matrix. This result can be used to compare variants of the waveform relaxation algorithm for solving initial value problems. The methods under consideration use the same discretization technique, but are based on multisplittings with different overlaps. Numerical experiments on the Intel iPSC/860 hypercube are included.     

Analysis of a non-linear difference scheme in reaction-diffusion

Summary A nonlinear partial difference equation resulting from discretising in space and time the parabolic reaction diffusion equation, which models the spruce budworm problem, is analysed and accuracy estimates obtained for solutions over afinite time range and ast. Although the analysis is restricted to the logistic model in one space dimension, the techniques and comparison principles developed in the paper should prove useful in assessing the merits of numerical solutions of other nonlinear parabolic difference equations.During the period of this research Professor Guo Ben Yu was supported by a Science and Engineering Research Council visiting fellowship     

A parallel projection method for overdetermined nonlinear systems of equations

We consider overdetermined nonlinear systems of equationsF(x)=0, whereF: ^{n m} ,mn. For this type of systems we define weighted least square distance (WLSD) solutions, which represent an alternative to classical least squares solutions and to other solutions based on residual normas. We introduce a generalization of the classical method of Cimmino for linear systems and we prove local convergence results. We introduce a practical strategy for improving the global convergence properties of the method. Finally, numerical experiments are presented.Work supported by FAPESP (Grant 90/3724/6), FINEP, CNPq and FAEP-UNICAMP.     

An invariance principle for the local time of a recurrent random walk

Summary Let (S _j ) be a lattice random walk, i.e. S _j =X ₁ +...+X _j , where X ₁,X ₂,... are independent random variables with values in the integer lattice and common distribution F, and let , the local time of the random walk at k before time n. Suppose EX ₁=0 and F is in the domain of attraction of a stable law G of index > 1, i.e. there exists a sequence a(n) (necessarily of the form n ¹l(n), where l is slowly varying) such that S _n /a(n) G. Define , where c(n)=a(n/log log n) and [x] = greatest integer x. Then we identify the limit set of {g _n (, ·) n1} almost surely with a nonrandom set in terms of the I-functional of Donsker and Varadhan.The limit set is the one that Donsker and Varadhan obtain for the corresponding problem for a stable process. Several corollaries are then derived from this invariance principle which describe the asymptotic behavior of L _n (, ·) as n.Research partially supported by NSF Grant #MCS 78-01168. These results were announced at the Fifteenth European Meeting of Statisticians, Palermo, Italy (September, 1982)     

Numerical application of Euler's series transformation and its generalizations

Summary A nonlinear generalizationÊ _z of Euler's series transformation is compared with the (linear) Euler-Knopp transformationE _z and a twoparametric methodE . It is shown how to applyE orE _, to compute the valuef(z_o) of a functionf from the power series at 0 iff is holomorphic in a half plane or in the cut plane. BothE andE _, are superior toÊ _z . A compact recursive algorithm is given for computingE andE _,.     

Nonlinear eigenvalue approximation

Summary For each in some domainD in the complex plane, letF() be a linear, compact operator on a Banach spaceX and letF be holomorphic in . Assuming that there is a so thatI–F() is not one-to-one, we examine two local methods for approximating the nonlinear eigenvalue . In the Newton method the smallest eigenvalue of the operator pencil [I–F(),F()] is used as increment. We show that under suitable hypotheses the sequence of Newton iterates is locally, quadratically convergent. Second, suppose 0 is an eigenvalue of the operator pencil [I–F(),I] with algebraic multiplicitym. For fixed leth() denote the arithmetic mean of them eigenvalues of the pencil [I–F(),I] which are closest to 0. Thenh is holomorphic in a neighborhood of andh()=0. Under suitable hypotheses the classical Muller's method applied toh converges locally with order approximately 1.84.     

Small compact perturbation of strongly irreducible operators

An operatorT onH is called strongly irreducible ifT is not similar to any reducible operators. In this paper, we shall say yes to answer the following question raised by D. A. Herrero.Given an operatorT with connected spectrum (T) and a positive number , can we find a compact operatorK with K < such thatT+K is strongly irreducible?Supported by National Natural Science Foundation of China(19901011), Mathematical Center of State Education Commission of China and 973 Project of China