On sum-product bases

We investigate additive-multiplicative bases in . Let , s>2, and . It is proved that , provided min {|B| ^s/2|A|^(s−2)/2,|A| ^s/2|B|^(s−2)/2}>p ^s/2. This note is supported by “Balaton Program Project” and OTKA grants K 61908, K 67676.     

Cutting-plane theory: Algebraic methods

This paper is a survey, with new results, of the algebraic approach to cutting-planes. The new results are a subadditive dual program for integer programs, and a generalization of R. Gomory's linear inequality characterization of the cuts valid for the group problem. We also provide some results on the large family of alternate group problems, in addition to the one group problem that is conventionally thought of in connection with the algebraic approach. In terms of expository material, we shall provide very concise proofs of the most well-known results in the basic papers of the algebraic approach. (Note: This is a revision of Part I of MSRR no. 370).     

Rosenbrock methods for Differential Algebraic Equations

Summary This paper deals with the numerical solution of Differential/Algebraic Equations (DAE) of index one. It begins with the development of a general theory on the Taylor expansion for the exact solutions of these problems, which extends the well-known theory of Butcher for first order ordinary differential equations to DAE's of index one. As an application, we obtain Butcher-type results for Rosenbrock methods applied to DAE's of index one, we characterize numerical methods as applications of certain sets of trees. We derive convergent embedded methods of order 4(3) which require 4 or 5 evaluations of the functions, 1 evaluation of the Jacobian and 1 LU factorization per step.     

Algebraic theory of multiplicative Schwarz methods

The convergence of multiplicative Schwarz-type methods for solving linear systems when the coefficient matrix is either a nonsingular M-matrix or a symmetric positive definite matrix is studied using classical and new results from the theory of splittings. The effect on convergence of algorithmic parameters such as the number of subdomains, the amount of overlap, the result of inexact local solves and of “coarse grid” corrections (global coarse solves) is analyzed in an algebraic setting. Results on algebraic additive Schwarz are also included.     

Algebraic multilevel preconditioning methods. I

Summary A recursive way of constructing preconditioning matrices for the stiffness matrix in the discretization of selfadjoint second order elliptic boundary value problems is proposed. It is based on a sequence of nested finite element spaces with the usual nodal basis functions. Using a nodeordering corresponding to the nested meshes, the finite element stiffness matrix is recursively split up into two-level block structures and is factored approximately in such a way that any successive Schur complement is replaced (approximated) by a matrix defined recursively and thereform only implicitely given. To solve a system with this matrix we need to perform a fixed number (v) of iterations on the preceding level using as an iteration matrix the preconditioning matrix already defined on that level. It is shown that by a proper choice of iteration parameters it suffices to use \left( {1 - \gamma ^2 } \right)^{ - \tfrac{1}{2}} $$ " align="middle" border="0"> iterations for the so constructedv-foldV-cycle (wherev=2 corresponds to aW-cycle) preconditioning matrices to be spectrally equivalent to the stiffness matrix. The conditions involve only the constant in the strengthened C.-B.-S. inequality for the corresponding two-level hierarchical basis function spaces and are therefore independent of the regularity of the solution for instance. If we use successive uniform refinements of the meshes the method is of optimal order of computational complexity, if . Under reasonable assumptions of the finite element mesh, the condition numbers turn out to be so small that there are in practice few reasons to use an accelerated iterative method like the conjugate gradient method, for instance.Dedicated to the memory of Peter HenriciThe research of the second author reported here was supported in part by the Committee of Science, Bulgaria, under Grant No. 55/26.03.87     

Algebraic multigrid methods for Laplacians of graphs

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10⁶ vertices.     

A sum-product estimate in algebraic division algebras

LetA be a finite subset of some normed division algebra over ℝ with cardinality ⋎A⋎. We prove that either the sum set or the product set ofA has cardinality ⋎A⋎^1+δ for some δ>0. Partially supported by NSA grant No. MDA 904-03-1-0045.     

Algebraic methods in discrete analogs of the Kakeya problem

We prove the joints conjecture, showing that for any N lines in R³, there are at most points at which 3 lines intersect non-coplanarly. We also prove a conjecture of Bourgain showing that given N² lines in R³ so that no N lines lie in the same plane and so that each line intersects a set P of points in at least N points then the cardinality of the set of points is Ω(N³). Both our proofs are adaptations of Dvir's argument for the finite field Kakeya problem.     

A sum-product theorem in semi-simple commutative Banach algebras

The following analogue of the Erdös-Szemerédi sum-product theorem is shown. Let A=f₁,?,f_N be a finite set of N arbitrary distinct functions on some set. Then either the sum set f_i+f_j or the product set has at least N^1+c elements, where c>0 is an absolute constant. We use Freiman's lemma and Balog-Szemerédi-Gowers Theorem on graphs and combinatorics.As a corollary, we obtain an Erdös-Szemerédi type theorem for semi-simple commutative Banach algebras R. Thus if A⊂R is a finite set, |A| large enough, then

|A+A|+|A.A|>|A|1+c,     

An application of kissing number in sum-product estimates

The boundedness of the kissing numbers of convex bodies has been known to Hadwiger [9] for long. We present an application of it to the sum-product estimate

$$\max(\mid{\mathcal{A}+\mathcal{A}}\mid,\mid{\mathcal{A}\mathcal{A}}\mid)\gg \frac {\mid{\mathcal{A}\mid}^{4/3}}{\lceil\log\mid{\mathcal{A}\mid}\rceil^{1/3}}$$

for finite sets \({\mathcal{A}}\) of quaternions and of a certain family of well-conditioned matrices.

     

The discretized sum-product and projection theorems

We give a new presentation of the discrete ring theorem for sets of real numbers [B]. Special attention is given to the relation between the various parameters. As an application, new Marstrand type projection theorems are obtained and formulated either in terms of box or Hausdorff dimension. It is shown that the dimension of the projections satisfies a nontrivial lower bound outside a very sparse set of exceptional directions.     

Algebraic methods for the solution of linear functional equations

The equation

$$\sum^{n}_ {i=0} a_{i}f(b_{i}x + (1 - b_{i})y) = 0$$

belongs to the class of linear functional equations. The solutions form a linear space with respect to the usual pointwise operations. According to the classical results of the theory they must be generalized polynomials. New investigations have been started a few years ago. They clarified that the existence of non-trivial solutions depends on the algebraic properties of some related families of parameters. The problem is to find the necessary and sufficient conditions for the existence of non-trivial solutions in terms of these kinds of properties. One of the earliest results is due to Z. Daróczy [1]. It can be considered as the solution of the problem in case of n = 2. We are going to take more steps forward by solving the problem in case of n = 3.