An adaptive finite element method for singular parabolic equations

Summary. In this paper we consider additive Schwarz-type iteration methods for saddle point problems as smoothers in a multigrid method. Each iteration step of the additive Schwarz method requires the solutions of several small local saddle point problems. This method can be viewed as an additive version of a (multiplicative) Vanka-type iteration, well-known as a smoother for multigrid methods in computational fluid dynamics. It is shown that, under suitable conditions, the iteration can be interpreted as a symmetric inexact Uzawa method. In the case of symmetric saddle point problems the smoothing property, an important part in a multigrid convergence proof, is analyzed for symmetric inexact Uzawa methods including the special case of the additive Schwarz-type iterations. As an example the theory is applied to the Crouzeix-Raviart mixed finite element for the Stokes equations and some numerical experiments are presented. Mathematics Subject Classification (1991):65N22, 65F10, 65N30Supported by the Austrian Science Foundation (FWF) under the grant SFB F013}\and Walter Zulehner     

Two-level preconditioners for regularized inverse problems I: Theory

Summary. We compare additive and multiplicative Schwarz preconditioners for the iterative solution of regularized linear inverse problems, extending and complementing earlier results of Hackbusch, King, and Rieder. Our main findings are that the classical convergence estimates are not useful in this context: rather, we observe that for regularized ill-posed problems with relevant parameter values the additive Schwarz preconditioner significantly increases the condition number. On the other hand, the multiplicative version greatly improves conditioning, much beyond the existing theoretical worst-case bounds. We present a theoretical analysis to support these results, and include a brief numerical example. More numerical examples with real applications will be given elsewhere. Received May 28, 1998 / Published online: July 7, 1999     

On Schwarz's domain decomposition methods for elliptic boundary value problems

Summary. We study the additive and multiplicative Schwarz domain decomposition methods for elliptic boundary value problem of order 2 r based on an appropriate spline space of smoothness . The finite element method reduces an elliptic boundary value problem to a linear system of equations. It is well known that as the number of triangles in the underlying triangulation is increased, which is indispensable for increasing the accuracy of the approximate solution, the size and condition number of the linear system increases. The Schwarz domain decomposition methods will enable us to break the linear system into several linear subsystems of smaller size. We shall show in this paper that the approximate solutions from the multiplicative Schwarz domain decomposition method converge to the exact solution of the linear system geometrically. We also show that the additive Schwarz domain decomposition method yields a preconditioner for the preconditioned conjugate gradient method. We tested these methods for the biharmonic equation with Dirichlet boundary condition over an arbitrary polygonal domain using cubic spline functions over a quadrangulation of the given domain. The computer experiments agree with our theoretical results. Received December 28, 1995 / Revised version received November 17, 1998 / Published online September 24, 1999     

A convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

The Mortar Element Method with Locally Nonconforming Elements

We consider a discretization of linear elliptic boundary value problems in 2-D by the new version of the mortar finite element method which uses locally nonconforming Crouzeix-Raviart elements. We show that if a solution of the original differential problem belongs to the space H ²(), then an error is of the same order as in the standard nonconforming finite element method. We also propose an additive Schwarz method of solving the discrete problem and show that its rate of convergence is almost optimal.     

Downward Sets and their separation and approximation properties

We develop a theory of downward subsets of the space ^I, where I is a finite index set. Downward sets arise as the set of all solutions of a system of inequalities x^I,f_t(x)0 (tT), where T is an arbitrary index set and each f _t (tT) is an increasing function defined on ^I. These sets play an important role in some parts of mathematical economics and game theory. We examine some functions related to a downward set (the distance to this set and the plus-Minkowski gauge of this set, which we introduce here) and study lattices of closed downward sets and of corresponding distance functions. We discuss two kinds of duality for downward sets, based on multiplicative and additive min-type functions, respectively, and corresponding separation properties, and we give some characterizations of best approximations by downward sets. Some links between the multiplicative and additive cases are established.     

A convergence theory for an overlapping Schwarz algorithm using discontinuous iterates

Summary. A new type of overlapping Schwarz methods, using discontinuous iterates, is constructed by modifying the classical overlapping Schwarz algorithm. This new algorithm allows for discontinuous iterates across the artificial interface. For Poissons equation, this algorithm can be considered as an overlapping version of Lions Robin iteration method for which little is known concerning the rate of convergence. Since overlap improves the performance of the classical algorithms considerably, the existence of a uniform convergence factor is the fundamental question for our algorithm. A new theory using Lagrange multipliers is developed and conditions are found for the existence of an almost uniform convergence factor for the dual variables, which implies rapid convergence of the primal variables, in the two overlapping subdomain case. Our result also shows a relation between the boundary conditions of the given problem and the artificial interface condition. Numerical results for the general case with cross points are also presented. They indicate possible extensions of our results to this more general case.Mathematics Subject Classification (2000): 65F10, 65N30, 65N55Acknowledgement I would like to thank my advisor Olof Widlund for suggesting this problem, for many helpful and interesting discussions, and for all his encouragement. I also thank the referees for their helpful corrections and suggestions.     

Multiplicative Difference Sets via Additive Characters

We use Fourier analysis on the additive group of to give an alternative proof of the recent theorem of Maschietti and to prove recent conjectures of No, Chung and Yun and No, Golomb, Gong, Lee and Gaal on difference sets in the multiplicative group of , m odd. Along the ay e prove a stronger form of a celebrated theorem of Welch on the 3-valued cross-correlation of maximal length sequences.     

Two perturbation bounds for singular values and eigenvalues

The relative error in as an approximation to α is measured by

On the distribution of the residues of small multiplicative subgroups of $$ \mathbb{F}_p $$

Distributional properties of small multiplicative subgroups of are obtained. In particular, it is shown that if H < is of size larger than polylogarithmic in p, then, letting β < 1 be a fixed exponent, most elements of any coset aH (a ∈ , arbitrary) will not fall into the interval [−p ^β, p ^β] ∈ . The arguments are based on the theory of heights and results from additive combinatoric.     

Multiplicative symmetry and related functional equations

Summary Let (G, *) be a commutative monoid. Following J. G. Dhombres, we shall say that a functionf: G G is multiplicative symmetric on (G, *) if it satisfies the functional equationf(x * f(y)) = f(y * f(x)) for allx, y inG. (1)Equivalently, iff: G G satisfies a functional equation of the following type:f(x * f(y)) = F(x, y) (x, y G), whereF: G × G G is a symmetric function (possibly depending onf), thenf is multiplicative symmetric on (G, *).In Section I, we recall the results obtained for various monoidsG by J. G. Dhombres and others concerning the functional equation (1) and some functional equations of the formf(x * f(y)) = F(x, y) (x, y G), (E) whereF: G × G G may depend onf. We complete these results, in particular in the case whereG is the field of complex numbers, and we generalize also some results by considering more general functionsF. In Section II, we consider some functional equations of the formf(x * f(y)) + f(y * f(x)) = 2F(x, y) (x, y K), where (K, +, ·) is a commutative field of characteristic zero, * is either + or · andF: K × K K is some symmetric function which has already been considered in Section I for the functional equation (E). We investigate here the following problem: which conditions guarantee that all solutionsf: K K of such equations are multiplicative symmetric either on (K, +) or on (K, ·)? Under such conditions, these equations are equivalent to some functional equations of the form (E) for which the solutions have been given in Section I. This is a partial answer to a question asked by J. G. Dhombres in 1973.     

Multiplicative Mappings of Rings

Let R and F be arbitrary associative rings. A mapping φ of R onto F is called a multiplicative isomorphism if φ is bijective and satisfies φ（xy） = φ（x）φ（y） for all x, y ∈ R. In this short note, we establish a condition on R, in the case where R may not contain any non-zero idempotents, that assures that φ is additive, which generalizes the famous Martindale＇s result. As an application, we show that under a mild assumption every multiplicative isomorphism from the radical of a nest algebra onto an arbitrary ring is additive.     

Probabilistic Number Theory in Additive Arithmetic Semigroups, III

We extend the investigation of quantitative mean-value theorems of completely multiplicative functions on additive arithmetic semigroups given in our previous paper. Then the new and old quantitative mean-value theorems are applied to the investigation of local distribution of values of a special additive function *(a). The result is unexpected from the point of view of classical number theory. This reveals the fact that the essential divergence of the theory of additive arithmetic semigroups from classical number theory is not related to the existence of a zero of the zeta function Z(y) at y = –q ^–1.     

Additive Schwarz Methods for Elliptic Mortar Finite Element Problems

Summary. Two variants of the additive Schwarz method for solving linear systems arising from the mortar finite element discretization on nonmatching meshes of second order elliptic problems with discontinuous coefficients are designed and analyzed. The methods are defined on subdomains without overlap, and they use special coarse spaces, resulting in algorithms that are well suited for parallel computation. The condition number estimate for the preconditioned system in each method is proportional to the ratio H/h, where H and h are the mesh sizes, and it is independent of discontinuous jumps of the coefficients. For one of the methods presented the choice of the mortar (nonmortar) side is independent of the coefficients.This work has been supported in part by the Norwegian Research Council, grant 113492/420This work has been supported in part by the National Science Foundation, grant NSF-CCR-9732208 and in part by the Polish Science Foundation, grant 2P03A02116 Mathematics Subject Classification (2000):65N55     

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)     

Overlapping restricted additive Schwarz method applied to the linear complementarity problem with?an?H-matrix

In this paper, a restricted additive Schwarz method is introduced for solving the linear complementarity problem that involves an H ₊-matrix. We show that the sequence generated by the restricted additive Schwarz method converges to the unique solution of the problem without any restriction on the initial point. Moreover, the comparison theorem is given between different versions of the restricted additive Schwarz method by using the weighted max-norm. We also show that the restricted additive Schwarz method is much better than the corresponding additive Schwarz variants in terms of the iteration number and the execution time.     

Additive Schwarz algorithms for the p version of the Galerkin boundary element method

Summary. We study some additive Schwarz algorithms for the version Galerkin boundary element method applied to some weakly singular and hypersingular integral equations of the first kind. Both non-overlapping and overlapping methods are considered. We prove that the condition numbers of the additive Schwarz operators grow at most as independently of h, where p is the degree of the polynomials used in the Galerkin boundary element schemes and h is the mesh size. Thus we show that additive Schwarz methods, which were originally designed for finite element discretisation of differential equations, are also efficient preconditioners for some boundary integral operators, which are non-local operators. Received June 15, 1997 / Revised version received July 7, 1998 / Published online February 17, 2000     

Preconditioners for nonsymmetric block toeplitz-like-plus-diagonal linear systems

Summary. We consider the system of linear equations Lu=f, where L is a nonsymmetric block Toeplitz-like-plus-diagonal matrix, which arises from the Sinc-Galerkin discretization of differential equations. Our main contribution is to construct effective preconditioners for this structured coefficient matrix and to derive tight bounds for eigenvalues of the preconditioned matrices. Moreover, we use numerical examples to show that the new preconditioners, when applied to the preconditioned GMRES method, are efficient for solving the system of linear equations. Mathematics Subject Classification (2000):65F10, 65F15, 65T10Research subsidized by The Special Funds for Major State Basic Research Projects G1999032803Research supported in part by RGC Grant Nos. 7132/00P and 7130/02P, and HKU CRCG Grant Nos 10203501, 10203907 and 10203408     

Planar homogeneous systems of difference equations

This paper is concerned to additive and multiplicative systems of homogeneous difference equations of non‐negative degree. We apply a reduction in order for both additive and multiplicative systems. Then, we consider convergence and monotony of positive solutions. In fact, using convergence results on factor maps, we obtain convergence results on homogeneous systems. We will conclude that monotonic behaviour on the invariant ray (i.e. for multiplicative systems and for additive systems) may or may not be the representative of other solutions. To illustrate our results, some examples are presented by multiplicative and additive homogeneous systems of rational equations. Copyright © 2014 John Wiley & Sons, Ltd.