Convergence analysis and error estimates for a parallel algorithm for solving the Navier-Stokes equations

Summary. This paper is concerned with the analysis of the convergence and the derivation of error estimates for a parallel algorithm which is used to solve the incompressible Navier-Stokes equations. As usual, the main idea is to split the main differential operator; this allows to consider independently the two main difficulties, namely nonlinearity and incompressibility. The results justify the observed accuracy of related numerical results. Received April 20, 2001 / Revised version received May 21, 2001 / Published online March 8, 2002 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain) Proyecto PB96–0986     

A likelihood-MPEC approach to target classification

In this paper we develop a method for classifying an unknown data vector as belonging to one of several classes. This method is based on the statistical methods of maximum likehood and borrowed strength estimation. We develop an MPEC procedure (for Mathematical Program with Equilibrium Constraints) for the classification of a multi-dimensional observation, using a finite set of observed training data as the inputs to a bilevel optimization problem. We present a penalty interior point method for solving the resulting MPEC and report numerical results for a multispectral minefield classification application. Related approaches based on conventional maximum likehood estimation and a bivariate normal mixture model, as well as alternative surrogate classification objective functions, are described. Received: October 26, 1998 / Accepted: June 11, 2001?Published online March 24, 2003 RID="***" ID="***"The authors of this work were all partially supported by the Wright Patterson Air Force Base via Veda Contract F33615-94-D-1400. The first and third author were also supported by the National Science Foundation under grant DMS-9705220. RID="*" ID="*"The work of this author was based on research supported by the U.S. National Science Foundation under grant CCR-9624018. RID="**" ID="**"The work of this author was supported by the Office of Naval Research under grant N00014-95-1-0777.     

Error bounds for minimal energy bivariate polynomial splines

Summary. We derive error bounds for bivariate spline interpolants which are calculated by minimizing certain natural energy norms. Received March 28, 2000 / Revised version received June 23, 2000 / Published online March 8, 2002 RID="*" ID="*" Supported by the National Science Foundation under grant DMS-9870187 RID="**" ID="**" Supported by the National Science Foundation under grant DMS-9803340 and by the Army Research Office under grant DAAD-19-99-1-0160     

On the convergence of the Weiszfeld algorithm

In this work we analyze the paper “Brimberg, J. (1995): The Fermat-Weber location problem revisited. Mathematical Programming 71, 71–76” which claims to close the question on the conjecture posed by Chandrasekaran and Tamir in 1989 on the convergence of the Weiszfeld algorithm. Some counterexamples are shown to the proofs showed in Brimberg’s paper. Received: January 1999 / Accepted: December 2001?Published online April 12, 2002 RID="*" ID="*"Partially supported by PB/11/FS/97 of Fundación Séneca of the Comunidad Autónoma de la Región de Murcia RID="**" ID="**"Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+I+D), project TIC2000-1750-C06-06 RID="*" RID="**"     

Effects of uncertainties in the domain on the solution of Dirichlet boundary value problems

Summary. A domain with possibly non-Lipschitz boundary is defined as a limit of monotonically expanding or shrinking domains with Lipschitz boundary. A uniquely solvable Dirichlet boundary value problem (DBVP) is defined on each of the Lipschitz domains and the limit of these solutions is investigated. The limit function also solves a DBVP on the limit domain but the problem can depend on the sequences of domains if the limit domain is unstable with respect to the DBVP. The core of the paper consists in estimates of the difference between the respective solutions of the DBVP on two close domains, one of which is Lipschitz and the other can be unstable. Estimates for starshaped as well as rather general domains are derived. Their numerical evaluation is possible and can be done in different ways. Received October 16, 2001 / Revised version received January 16, 2002 / Published online: April 17, 2002 RID="*" ID="*" The research was funded partially by the National Science Foundation under the grants NSF–Czech Rep. INT-9724783 and NSF DMS-9802367 RID="**" ID="**" Support for Jan Chleboun coming from the Grant Agency of the Czech Republic through grant 201/98/0528 is appreciated     

Combinatorial and Arithmetical Properties of Linear Numeration Systems

Dedicated to the memory of Paul Erdős We extend a result of J. Alexander and D. Zagier on the Garsia entropy of the Erdős measure. Our investigation heavily relies on methods from combinatorics on words. Furthermore, we introduce a new singular measure related to the Farey tree. Received October 7, 1999 RID="†" ID="†" This author is supported by the START-project Y96-MAT of the Austrian Science Fund RID="‡" ID="‡" This author is supported by the Austrian Science Fund (FWF) grant P14200-MAT RID="*" ID="*" This author is supported by the Austrian Science Fund (FWF) grant S8307-MAT     

The Baum-Connes conjecture for hyperbolic groups

We prove the Baum-Connes conjecture for hyperbolic groups and their subgroups. Oblatum 20-VI-2001 & 24-VIII-2001?Published online: 15 April 2002 RID="*" ID="*"The second author is partially supported by NSF and MSRI.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

On preconditioned Uzawa methods and SOR methods for saddle-point problems

This paper studies convergence analysis of a preconditioned inexact Uzawa method for nondifferentiable saddle-point problems. The SOR-Newton method and the SOR-BFGS method are special cases of this method. We relax the Bramble-Pasciak-Vassilev condition on preconditioners for convergence of the inexact Uzawa method for linear saddle-point problems. The relaxed condition is used to determine the relaxation parameters in the SOR-Newton method and the SOR-BFGS method. Furthermore, we study global convergence of the multistep inexact Uzawa method for nondifferentiable saddle-point problems.     

A generalization of parameterized inexact Uzawa method for generalized saddle point problems

Recently, a class of parameterized inexact Uzawa methods has been proposed for generalized saddle point problems by Bai and Wang [Z.-Z. Bai, Z.-Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008) 2900–2932], and a generalization of the inexact parameterized Uzawa method has been studied for augmented linear systems by Chen and Jiang [F. Chen, Y.-L. Jiang, A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput. (2008)]. This paper is concerned about a generalization of the parameterized inexact Uzawa method for solving the generalized saddle point problems with nonzero (2, 2) blocks. Some new iterative methods are presented and their convergence are studied in depth. By choosing different parameter matrices, we derive a series of existing and new iterative methods, including the preconditioned Uzawa method, the inexact Uzawa method, the SOR-like method, the GSOR method, the GIAOR method, the PIU method, the APIU method and so on. Numerical experiments are used to demonstrate the feasibility and effectiveness of the generalized parameterized inexact Uzawa methods.     

A primal all-integer algorithm based on irreducible solutions

 This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method. Received: April 23, 2001 / Accepted: May 2002 Published online: March 21, 2003 RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="#" ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202. Mathematics Subject Classification (1991): 90C10     

Large Cliques in -Free Graphs

Dedicated to the memory of Paul Erdős A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs. Received October 25, 1999 RID="*" ID="*" Supported by OTKA grant T029074. RID="**" ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203.     

Homotopy equivalences of p-completed classifying spaces of finite groups

We study homotopy equivalences of p-completions of classifying spaces of finite groups. To each finite group G and each prime p, we associate a finite category ℒ _p ^c (G) with the following properties. Two p-completed classifying spaces BG _p ^∧ and BG’ _p ^∧ have the same homotopy type if and only if the associated categories ℒ _p ^c (G) and ℒ _p ^c (G’) are equivalent. Furthermore, the topological monoid Aut(BG _p ^∧) of self equivalences is determined by the self equivalences of the associated category ℒ _p ^c (G). Oblatum 5-VII-2001 & 28-VIII-2002?Published online: 8 November 2002 RID="*" ID="*"C. Broto is partially supported by DGICYT grant PB97–0203. RID="**" ID="**"R. Levi is partially supported by EPSRC grant GR/M7831. RID="***" ID="***"B. Oliver is partially supported by UMR 7539 of the CNRS.     

Uzawa methods for a class of block three‐by‐three saddle‐point problems

In this work, we consider numerical methods for solving a class of block three‐by‐three saddle‐point problems, which arise from finite element methods for solving time‐dependent Maxwell equations and some other applications. The direct extension of the Uzawa method for solving this block three‐by‐three saddle‐point problem requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, we propose an inexact Uzawa method, which solves the symmetric indefinite linear system in some inexact way. Under suitable assumptions, we show that the inexact Uzawa method converges to the unique solution of the saddle‐point problem within the approximation level. Two special algorithms are customized for the inexact Uzawa method combining the splitting iteration method and a preconditioning technique, respectively. Numerical experiments are presented, which demonstrated the usefulness of the inexact Uzawa method and the two customized algorithms.     

Buyer-seller exactness in the assignment game

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a “45^o-lattice” by means of the core of an assignment game can now be answered. Received: March 2002/Revised version: January 2003 RID="*" ID="*"  Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged RID="**" ID="**"  The authors thank the referees for their comments     

Some observations on Babu\vs}ka and Brezzi theories

Summary. Some observations are made on abstract error estimates for Galerkin approximations based on Babuška-Brezzi conditions. A basic error estimate due to Babuška is sharpened by means of an identity that for any nontrivial idempotent operator P. Some remarks are also made on the Brezzi's theory for mixed variational problems and their Galerkin approximations. Received March 1, 2000 / Revised version received September 28, 2000 / Published online June 17, 2002 RID="*" ID="*" This work was partially supported by NSF DMS-9706949, NSF ACI-9800244 and NASA NAG2-1236 Correspondence to: J. Xu