Preprint Series 1998
-
1998:01
S. BrennerLower bounds for two-level additive Schwarz preconditioners with small overlap (file not available)
(SIAM J. Sci. Comp. 21 (2000), 1657-1669.)
Lower bounds for the condition numbers of the preconditioned systems are obtained for two-level additive Schwarz preconditioners for both second order and fourth order problems. They show that the known upper bounds are sharp in the case of a small overlap.
[Full Abstract] -
1998:02
R. DeVore
This is a survey of nonlinear approximation, especially that part of the subject which is important in numerical computation. Nonlinear approximation means that the approximants do not come from linear spaces but rather from nonlinear manifolds. The central question to be studied is what, if any, are the advantages of ...
[Full Abstract] -
1998:03
K. Oskolkov
Our goal is to compare the efficiencies of linear and nonlinear methods in the problem of ridge approximation. We confine ourselves by functions of two variables $f(x)=f(x _ 1,x _ 2)$ and the norm $\|\cdot\|$ of Hilbert space $L^2(\mathbb{B}^2)$, where $\mathbb{B ...
[Full Abstract] -
1998:04
S. Brenner and
L. SungLower bounds for nonoverlapping domain decomposition preconditioners in two dimensions (file not available)
(Math. Comp. 69 (2000), 1319-1339)
Lower bounds for the condition numbers of the preconditions systems are obtained for the Bramble-Pasciak-Schatz substructuring preconditioner and the Neumann-Neumann preconditioner in two dimensions. They show that the known upper bounds are sharp.
[Full Abstract] -
1998:05
S. Brenner and
L. SungLower bounds for two-level additive Schwarz preconditioners for nonconforming finite elements (file not available)
(Advances in Computational Mathematics (Proceedings of the Guangzhou International Symposium 1997) Lecture Notes in Pure and Appl. Math. 202, pp. 585-604, Dekker, New York, 1999)
Lower bounds for the condition numbers of the preconditioned systems are obtained for two-level additive Schwarz preconditioners for nonconforming nite element methods. They show that ...
[Full Abstract] -
1998:06
K. Oskolkov
The goal is to compare free (non-linear), equispaced ridge and algebraic polynomial approximations $R^{\textrm{fr}} _ N[f]$, $R^{\textrm{eq}} _ N[f]$, $E _ N[f]$ of individual functions $f(x)$ in the norm of $L^2(\mathbb{B}^2),\mathbb{B}^2$ - the unit disc $|x ...
[Full Abstract] -
1998:07
S. BrennerA nonstandard finite element interpolation estimate (file not available)
(Numer. Funct. Anal. Optim. 20 (1999), 245-250)
We show that $\|u _ I\|H^{l+e}(\Omega)\leq{C}\|u\|H^{l+e}(\Omega)$, where $\Omega$ is a bounded polygonal domain in $R^20<\epsilon<(\frac{1}{2})$, $u _ 1$ is the piecewise linear nodal interpolant of u with ...
[Full Abstract] -
1998:08
F. Chudak and
J. Griggs
P. L. Erdős and G.O.H. Katona gave an inequality involving binomial coefficients summed over an antichain in the product of two chains. Her we present the common generalization of this inequality and Lubell’s famous inequality for the Boolean lattice to an arbitrary product of chains (lattice of ...
[Full Abstract] -
1998:09
J. Griggs and
K. Reid
Two new elementary proofs are given of Landau's Theorem on necessary and sufficient conditions for a sequence of integers to be the score sequence for some tournament. The first is related to existing proofs by majorization, but it avoids depending on any facts about majorization. The second is natural ...
[Full Abstract] -
1998:10
J. Griggs and
G. Rote
n analogue of the Littlewood-Offord problem posed by the first author is to find the maximum number of subset sums equal to the same vector over all ways of selecting n vectors in $R^d$ in general position. This note reviews past progress and motivation for this problem, and presents ...
[Full Abstract] -
1998:11
J. Griggs and
C. Ho
Consider the minimum number $f(m,n)$ of zeroes in a $2m\times2n(0,1)$-matrix M that contains no $m\times{n}$ submatrix of ones. This special case of the well-known Zarankiewicz problem was studied by Griggs and Ouyang, who showed, for $m\leq{n}$, that $2n+m+1 ...
[Full Abstract] -
1998:12
J. Griggs and
C. Ho
In "Bulgarian Solitaire," a player divides a deck of n cards into piles. Each move consists of taking a card from each pile to form a single new pile. One is concerned only with how many piles there are of each size. Starting from any division into piles, one always ...
[Full Abstract] -
1998:13
J. Griggs,
M. Simonovits, and
G. Thomas
Let $Ex(n,k,\mu)$ denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most $\mu$ edges. Here we summarize some known results of the problem determining $Ex(n,k,\mu)$, give simple proofs, and find some new estimates ...
[Full Abstract] -
1998:14
J. Griggs
We discuss applications of combinatorial arguments to database security: maximizing the "usabiliby" of a statistical database under the control of the mechanism Audit Expert of Chin and Ozsoyoglu. As modeled by Mirka Miller et al., the goal is to maximize the number of SUM queries from a database of real ...
[Full Abstract] -
1998:15
A. Cohen,
W. Dahmen, and
R. DeVore
This paper is concerned with the construction and analysis of wavelet-based adaptive algorithms for the numerical solution of elliptic equations. These algorithms approximate the solution u of the equation by a linear combination of N wavelets. Therefore, a benchmark for their performance is provided by the rate of best approximation ...
[Full Abstract] -
1998:16
P. Erdős,
M. Steel,
L. Székely, and
T. Warnow
A phylogenetic tree (also called an "evolutionary tree") is a leaf–labeled tree which represents the evolutionary history for a set of species, and the construction of such trees is a fundamental problem in biology. Here we address the issue of how many sequence sites are required in order to ...
[Full Abstract] -
1998:17
P. Erdős,
M. Steel,
L. Székely, and
T. Warnow
Inferring evolutionary trees is an interesting and important problem in biology that is very difficult from a computational point of view as most associated optimization problems are NP-hard. Although it is known that many methods are provably statistically consistent (i.e. the probability of recovering the correct tree converges on ...
[Full Abstract] -
1998:18
F. Shahrokhi and
L. Székely
We study the integral uniform (multicommodity) flow problem in a graph G and construct a fractional solution whose properties are invariant under the action of a group of automorphisms Γ < Aut(G). The fractional solution is shown to be close to an integral solution (depending on properties of Γ), and ...
[Full Abstract] -
1998:19
F. Shahrokhi,
O. Sykora,
L. Székely, and
I. Vrto
The bipartite crossing number problem is studied, and a connection between this problem and the linear arrangement problem is established. It is shown that when the arboricity is close to the minimum degree and the graph is not too sparse, then the optimal number of crossings has the same order ...
[Full Abstract] -
1998:20
F. Shahrokhi,
O. Sykora,
L. Székely, and
I. Vrto
Let G be a connected bipartite graph. We give a short proof using the variation of Menger's Theorem, for a new lower bound which relates the bipartite crossing number of G, denoted by bcr(G), to the edge connectivity properties of G. The general lower bound implies a weaker ...
[Full Abstract] -
1998:21
P. Erdős,
K. Rice,
L. Székely, and
T. Warnow
Reconstruction phylogenetic (evolutionary) trees is a major research problem in biology, but unfortunately the current methods are either inconsistent somewhere in the parapeter space (and hence do not reconstruct the tree even given unboundedly long sequences), have poor statistical power (and hence require extremely long sequences on large or highly ...
[Full Abstract] -
1998:22
V. Temlyakov
The paper contains two theorems on approximation of functions with bounded mixed derivative. These theorems give some progress in two old open problems. The first one gives, in particular, an upper estimate in the Bernstein $L-1$-inequality for trigonometric polynomials on two variables with harmonics in hyperbolic crosses. The second ...
[Full Abstract] -
1998:23
V. Temlyakov
The question of finding an optimal dictionary for nonlinear m-term approximation is studied in the paper. We consider this problem in the periodic multivariate (d variables) case for classes of functions with mixed smoothness. We prove that the well known dictionary Ud which consists of trigonometric polynomials (shifts ...
[Full Abstract] -
1998:24
R. Getsadze
Let
$$\mathbb{B}^2:=\left\{|(x,y)\in{R}^2:x^2+y^2\leq1\right\}$$
denote the unit disc on the plane and
$$u _ mt:=\left.\frac{1}{\sqrt{\pi}}\frac{\sin(m+1)\arccos{t}}{\sqrt{1-t^2}}\right.,$$
$m=0,1,\ldots,t\in[-1,1 ...
[Full Abstract] -
1998:25
P. Petrushev
We prove in this paper the existence of a Schauder basis for $C[0,1]$ consisting of rational functions of uniformly bounded degrees. This solves an open question of some years concerning the possible existence of such bases. This result follows from a more general construction of bases on $I ...
[Full Abstract]
