The Durand-Kerner polynomials roots-finding method in case of multiple roots

The convergence of the Durand-Kerner algorithm is quadratic in case of simple roots but only linear in case of multiple roots. This paper shows that, at each step, the mean of the components converging to the same root approaches it with an error proportional to the square of the error at the previous step. Since it is also shown that it is possible to estimate the multiplicity order of the roots during the algorithm, a modification of the Durand-Kerner iteration is proposed to preserve a quadratic-like convergence even in case of multiple zeros.This work is supported in part by the Research Program C3 of the French CNRS and MEN, and by the Direction des Recherches et Etudes Techniques (DGA).     

A convergent scheme for a non local Hamilton Jacobi equation modelling dislocation dynamics

We study dislocation dynamics with a level set point of view. The model we present here looks at the zero level set of the solution of a non local Hamilton Jacobi equation, as a dislocation in a plane of a crystal. The front has a normal speed, depending on the solution itself. We prove existence and uniqueness for short time in the set of continuous viscosity solutions. We also present a first order finite difference scheme for the corresponding level set formulation of the model. The scheme is based on monotone numerical Hamiltonian, proposed by Osher and Sethian. The non local character of the problem makes it not monotone. We obtain an explicit convergence rate of the approximate solution to the viscosity solution. We finally provide numerical simulations.This work has been supported by funds from ACI JC 1041 “Mouvements d’interfaces avec termes non-locaux”, from ACI-JC 1025 “Dynamique des dislocations” and from ONERA, Office National d’Etudes et de Recherches. The second author was also supported by the ENPC-Région Ile de France.     

A generalization of the Runge–Kutta iteration

Iterative solvers in combination with multi-grid have been used extensively to solve large algebraic systems. One of the best known is the Runge–Kutta iteration. We show that a generally used formulation [A. Jameson, Numerical solution of the Euler equations for compressible inviscid fluids, in: F. Angrand, A. Dervieux, J.A. Désidéri, R. Glowinski (Eds.), Numerical Methods for the Euler Equations of Fluid Dynamics, SIAM, Philadelphia, 1985, pp. 199–245] does not allow to form all possible polynomial transmittance functions and we propose a new formulation to remedy this, without using an excessive number of coefficients.     

Numerical simulation of fluid-structure interaction problems on hybrid meshes with algebraic multigrid methods

Fluid-structure interaction problems arise in many fields of application such as flows around elastic structures and blood flow in arteries. The method presented in this paper for solving such a problem is based on a reduction to an equation at the interface, involving the so-called Steklov-Poincaré operators. This interface equation is solved by a Newton iteration, for which directional derivatives involving shape derivatives with respect to the interface perturbation have to be evaluated appropriately. One step of the Newton iteration requires the solution of several decoupled linear sub-problems in the structure and the fluid domains. These sub-problems are spatially discretized by a finite element method on hybrid meshes. For the time discretization, implicit first-order methods are used for both sub-problems. The discretized equations are solved by algebraic multigrid methods.     

Finite dimensional approximation of nonlinear problems

Summary In the first two papers of this series [4, 5], we have studied a general method of approximation of nonsingular solutions and simple limit points of nonlinear equations in a Banach space. We derive here general approximation results of the branches of solutions in the neighborhood of a simple bifurcation point. The abstract theory is applied to the Galerkin approximation of nonlinear variational problems and to a mixed finite element approximation of the von Kármán equations.The work of F. Brezzi has been completed during his stay at the Université P. et M. Curie and at the Ecole PolytechniqueThe work of J. Rappaz has been supported by the Fonds National Suisse de la Recherche Scientifique     

Individual and collective rationality in a dynamic Pareto equilibrium

This paper deals with the problem of establishing the conditions for individual and collective rationality when a set of players cooperate in a Pareto equilibrium. To derive such conditions one follows the approach of the theory of reachability of perturbed systems. Open-loop and closed-loop concepts are discussed and are shown to be nonequivalent.The research of the first author was supported in part by Canada Council Grant No. S-701-491 and has benefited from collaboration with the Laboratoire d'Automatique Théorique de l'Université de Paris VII, Paris, France.     

Convergence rate estimate for a domain decomposition method

Summary We provide a convergence rate analysis for a variant of the domain decomposition method introduced by Gropp and Keyes for solving the algebraic equations that arise from finite element discretization of nonsymmetric and indefinite elliptic problems with Dirichlet boundary conditions in ². We show that the convergence rate of the preconditioned GMRES method is nearly optimal in the sense that the rate of convergence depends only logarithmically on the mesh size and the number of substructures, if the global coarse mesh is fine enough.This author was supported by the National Science Foundation under contract numbers DCR-8521451 and ECS-8957475, by the IBM Corporation, and by the 3M Company, while in residence at Yale UniversityThis author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under Contract W-31-109-Eng-38This author was supported by the National Science Foundation under contract number ECS-8957475, by the IBM Corporation, and by the 3M Company     

The hierarchical basis multigrid method for convection-diffusion equations

Summary We make a theoretical study of the application of a standard hierarchical basis multigrid iteration to the convection diffusion equation, discretized using an upwind finite element discretizations. We show behavior that in some respects is similar to the symmetric positive definite case, but in other respects is markedly different. In particular, we find the rate of convergence depends significantly on parameters which measure the strength of the upwinding, and the size of the convection term. Numerical calculations illustrating some of these effects are given.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.     

Combined finite element and spectral approximation of the Navier-Stokes equations

Summary We present a method for the numerical approximation of Navier-Stokes equations with one direction of periodicity. In this direction a Fourier pseudospectral method is used, in the two others a standard F.E.M. is applied. We prove optimal rate of convergence where the two parameters of discretization intervene independently.

---

Approximation des équations de Navier-Stokes par une méthode éléments finis-spectrale Fourier

Resumé On présente une méthode d'approximation numérique des équations de Navier-Stokes possédant une direction de périodicité. Dans cette direction une méthode pseudospectrale basée sur des développements en série de Fourier est utilisée, dans les deux autres on applique une méthode d'éléments finis standard. On montre que la convergence est optimale et que les deux paramètres de discrétisation peuvent être choisis de façon indépendante.

     

Convergence and optimization of the parallel method of simultaneous directions for the solution of elliptic problems

For the solution of elliptic problems, fractional step methods and in particular alternating directions (ADI) methods are iterative methods where fractional steps are sequential. Therefore, they only accept parallelization at low level. In [T. Lu, P. Neittaanmäki, X.C. Tai, A parallel splitting-up method for partial differential equations and its applications to Navier–Stokes equations, RAIRO Modél. Math. Anal. Numér. 26 (6) (1992) 673–708], Lu et al. proposed a method where the fractional steps can be performed in parallel. We can thus speak of parallel fractional step (PFS) methods and, in particular, simultaneous directions (SDI) methods. In this paper, we perform a detailed analysis of the convergence and optimization of PFS and SDI methods, complementing what was done in [T. Lu, P. Neittaanmäki, X.C. Tai, A parallel splitting-up method for partial differential equations and its applications to Navier–Stokes equations, RAIRO Modél. Math. Anal. Numér. 26 (6) (1992) 673–708]. We describe the behavior of the method and we specify the good choice of the parameters. We also study the efficiency of the parallelization. Some 2D, 3D and high-dimensional tests confirm our results.     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

Multilevel Schwarz methods

Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland.     

Finite dimensional approximation of nonlinear problems

Summary We continue here the study of a general method of approximation of nonlinear equations in a Banach space yet considered in [2]. In this paper, we give fairly general approximation results for the solutions in a neighborhood of a simple limit point. We the apply the previous analysis to the study of Galerkin approximations for a class of variationally posed nonlinear problems and to a mixed finite element method for the NavierStokes equations.This work has been completed during a visit at the Université Pierre et Marie Curic and at the Ecole PolytechniqueSupported by the Fonds National Suisse de la Recherche Scientifique     

Approximation de quelques problèmes de type Stokes par une méthode d'éléments finis mixtes

Résumé Nous présentons dans cet article une méthode d'éléments finis mixtes qui permet la résolution des équations de Stokes avec des conditions aux limites de type Fourier ou Neumann. Pour cette méthode nous démontrons que les estimations de l'erreur d'approximation sont optimales; en vitesse et en pression. Ces résultats de convergences généralisent à ce type non standard de conditions aux limites les travaux de Glowinski-Pironneau [9, 10] pour le probleme de Stokes avec des conditions aux limites de Dirichlet.

---

Mixed-finite element approximation of stokes type problems

Summary We present in this paper a mixed-finite element approximation of Stokes equations with boundary conditions of Fourier's or Neumann's type. For this approximation we prove that the error estimates for the velocity-vector and for the pressure are optimal. These results of convergence generalize to this kind of boundary conditions the Glowinski-Pironneau's approximation of Stokes problem with Dirichlet's boundary conditions [9, 10].

     

Two new variants of nonlinear inexact Uzawa algorithms for saddle-point problems

Summary. In this paper, we consider some nonlinear inexact Uzawa methods for iteratively solving linear saddle-point problems. By means of a new technique, we first give an essential improvement on the convergence results of Bramble-Paschiak-Vassilev for a known nonlinear inexact Uzawa algorithm. Then we propose two new algorithms, which can be viewed as a combination of the known nonlinear inexact Uzawa method with the classical steepest descent method and conjugate gradient method respectively. The two new algorithms converge under very practical conditions and do not require any apriori estimates on the minimal and maximal eigenvalues of the preconditioned systems involved, including the preconditioned Schur complement. Numerical results of the algorithms applied for the Stokes problem and a purely linear system of algebraic equations are presented to show the efficiency of the algorithms. Received December 8, 1999 / Revised version received September 8, 2001 / Published online March 8, 2002 RID="*" ID="*" The work of this author was partially supported by a grant from The Institute of Mathematical Sciences, CUHK RID="**" ID="**" The work of this author was partially supported by Hong Kong RGC Grants CUHK 4292/00P and CUHK 4244/01P     

Finite element approximation of multi-scale elliptic problems using patches of elements

In this paper we present a method for the numerical solution of elliptic problems with multi-scale data using multiple levels of not necessarily nested grids. The method consists in calculating successive corrections to the solution in patches whose discretizations are not necessarily conforming. This paper provides proofs of the results published earlier (see C. R. Acad. Sci. Paris, Ser. I 337 (2003) 679–684), gives a generalization of the latter to more than two domains and contains extensive numerical illustrations. New results including the spectral analysis of the iteration operator and a numerical method to evaluate the constant of the strengthened Cauchy-Buniakowski-Schwarz inequality are presented. Supported by CTI Project 6437.1 IWS-IW.     

Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées

Résumé On considère la méthode de dissections emboîtées basée sur des théorèmes de séparation introduite par Gilbert-Tarjan et Roman utilisée pour la résolution par élimination de Gauss de grands systèmes linéaires creux. Plus précisemment, on étudie une structure de données par blocs similaire à celle proposée par George dans le cadre des graphes en grille, et on démontre les propriétés suivantes: d'une part, pour des familles de graphes à degré borné admettant unn -théorème de séparation, 1/2<1, le stockage secondaire de la structure par blocs contenant la matrice factorisée est linéaire par rapport à la taille du système; d'autre part, en rajoutant une hypothèse non restrictive sur la manière d'effectuer la séparation, la structure peut être construite en temps linéaire par une factorisation logique par blocs. Des exemples numériques illustrent ces résultats théoriques.

---

Algorithmic study and complexity bounds for a nested dissection solver

Summary We consider the nested dissection method based on separator theorems introduced by Gilbert-Tarjan and Roman used for solving large sparse systems of linear equations. More precisely, we study a block storage scheme such as proposed by George for regular square grids and we prove the following results: first, for families of graphs of bounded degree withn -separator theorem, 1/2<1, the overhead storage of the block data structure for the factored matrix is linear in system dimension; on the other hand, by adding a non restrictive assumption on the separation, this structure can be constructed by a block symbolic factorization which runs in time linear in matrix dimension. Numerical experiments illustrating these theoretical results are provided.

     

A survey of multilevel preconditioned iterative methods

We survey multilevel iterative methods applied for solving large sparse systems with matrices, which depend on a level parameter, such as arise by the discretization of boundary value problems for partial differential equations when successive refinements of an initial discretization mesh is used to construct a sequence of nested difference or finite element meshes.We discuss various two-level (two-grid) preconditioning techniques, including some for nonsymmetric problems. The generalization of these techniques to the multilevel case is a nontrivial task. We emphasize several ways this can be done including classical multigrid methods and a recently proposed algebraic multilevel preconditioning method. Conditions for which the methods have an optimal order of computational complexity are presented.On leave from the Institute of Mathematics, and Center for Informatics and Computer Technology, Bulgarian Academy of Sciences, Sofia, Bulgaria. The research of the second author reported here was partly supported by the Stichting Mathematisch Centrum, Amsterdam.     

A three-dimensional quadratic nonconforming element

Summary We define a second-degree nonconforming element on tetrahedra. We build a basis for the opproximation space derived from this element. We prove a discrete regularity property similar to the one that holds for the corresponding two-dimensional element.This work was partly supported by NSERC and by the Ministère de l'Education du Québec     

ADI preconditioned Krylov methods for large Lyapunov matrix equations

In the present paper, we propose preconditioned Krylov methods for solving large Lyapunov matrix equations AX+XA^T+BB^T=0. Such problems appear in control theory, model reduction, circuit simulation and others. Using the Alternating Direction Implicit (ADI) iteration method, we transform the original Lyapunov equation to an equivalent symmetric Stein equation depending on some ADI parameters. We then define the Smith and the low rank ADI preconditioners. To solve the obtained Stein matrix equation, we apply the global Arnoldi method and get low rank approximate solutions. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approaches.