Sine transform based preconditioners for elliptic problems

We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L + Σ)Σ⁻¹(L^t + Σ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Σ. We propose a preconditioner M = (Lˆ + Σˆ)Σˆ⁻¹(Lˆ^t + Σˆ) with block diagonal matrix Σˆ and lower block triangular matrix Lˆ. The diagonal blocks of Σˆ and the subdiagonal blocks of Lˆ are respectively the optimal sine transform approximations to the diagonal blocks of Σ and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O(n² log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M⁻¹A is of order O(1). In contrast, the system preconditioned by the MILU and MINV methods are of order O(n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed. © 1997 John Wiley & Sons, Ltd.     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Asymptotic Convergence of Conjugate Gradient Methods for the Partial Symmetric Eigenproblem

Recently an efficient method (DACG) for the partial solution of the symmetric generalized eigenproblem A x = δB x has been developed, based on the conjugate gradient (CG) minimization of the Rayleigh quotient over successive deflated subspaces of decreasing size. The present paper provides a numerical analysis of the asymptotic convergence rate ρ_j of DACG in the calculation of the eigenpair λ_j, u _j, when the scheme is preconditioned with A⁻¹. It is shown that, when the search direction are A-conjugate, ρ_j is well approximated by 4/ξ_j, where ξ_j is the Hessian condition number of a Rayleigh quotient defined in appropriate oblique complements of the space spanned by the leftmost eigenvectors u ₁, u ₂,…, u _j−1 already calculated. It is also shown that 1/ξ_j is equal to the relative separation between the eigenvalue λ_j currently sought and the next higher one λ_j+1 and the next higher one λ_{j + 1}. A modification of DACG (MDACG) is studied, which involves a new set of CG search directions which are made M-conjugate, with M-conjugate, with M-conjugate, with M a matrix approximating the Hessian. By distinction, MDACG has an asymptotic rate of convergence which appears to be inversely proportional to the square root of ξ_j, in complete agreement with the theoretical results known for the CG solution to linear systems. © 1997 by John Wiley & Sons, Ltd.     

Regular simplices and lower volume bounds for hyperbolicn-manifolds

For an-dimensional compact hyperbolic manifoldM ⁿ a new lower volume bound is presented. The estimate depends on the volume of a hyperbolic regularn-simplex of edge length equal to twice the in-radius ofM ⁿ. Its proof relies upon local density bounds for hyperbolic sphere packings.     

A comparison of abstract versions of deflation,balancing and additive coarse grid correction preconditioners

In this paper we consider various preconditioners for the conjugate gradient (CG) method to solve large linear systems of equations with symmetric positive definite system matrix. We continue the comparison between abstract versions of the deflation, balancing and additive coarse grid correction preconditioning techniques started in (SIAM J. Numer. Anal. 2004; 42 :1631–1647; SIAM J. Sci. Comput. 2006; 27 :1742–1759). There the deflation method is compared with the abstract additive coarse grid correction preconditioner and the abstract balancing preconditioner. Here, we close the triangle between these three methods. First of all, we show that a theoretical comparison of the condition numbers of the abstract additive coarse grid correction and the condition number of the system preconditioned by the abstract balancing preconditioner is not possible. We present a counter example, for which the condition number of the abstract additive coarse grid correction preconditioned system is below the condition number of the system preconditioned with the abstract balancing preconditioner. However, if the CG method is preconditioned by the abstract balancing preconditioner and is started with a special starting vector, the asymptotic convergence behavior of the CG method can be described by the so‐called effective condition number with respect to the starting vector. We prove that this effective condition number of the system preconditioned by the abstract balancing preconditioner is less than or equal to the condition number of the system preconditioned by the abstract additive coarse grid correction method. We also provide a short proof of the relationship between the effective condition number and the convergence of CG. Moreover, we compare the A‐norm of the errors of the iterates given by the different preconditioners and establish the orthogonal invariants of all three types of preconditioners. Copyright © 2008 John Wiley & Sons, Ltd.     

Hartley preconditioners for Toeplitz systems generated by positive continuous functions

In this paper, we consider the solution ofn-by-n symmetric positive definite Toeplitz systemsT _n x=b by the preconditioned conjugate gradient (PCG) method. The preconditionerM _n is defined to be the minimizer of T _n –B _{n F} over allB _n H _n whereH _n is the Hartley algebra. We show that if the generating functionf ofT _n is a positive 2-periodic continuous even function, then the spectrum of the preconditioned systemM _n ^–1 T _n will be clustered around 1. Thus, if the PCG method is applied to solve the preconditioned system, the convergence rate will be superlinear.     

Component behavior near the critical point of the random graph process

We study the behavior of a random graph process (G(n, M))₀²ⁿ for M(n) = n/2 + s and ∣s∣³n^?;2 → ∞. Among others we find the number of components in G(n, M) and estimate the number of vertices and edges in the kth largest component of G(n, M), for any natural number k, Moreover, it is shown that, with probability 1 –o(1), when M(n) = n/2 + s, s³n^?2 →?∞, then during a random graph process in some step M¹ > M a “new” largest component will emerge, whereas when s³n^?2→∞, the largest component of G(n, M) remains largest until the very end of the process.     

Some applications of Montgomery's sieve

Artin has conjectured that every positive integer not a perfect square is a primitive root for some odd prime. A new estimate is obtained for the number of integers in the interval [M + 1, M + N] which are not primitive roots for any odd prime, improving on a theorem of Gallagher.Erd?s has conjectured that 7, 15, 21, 45, 75, and 105 are the only values of the positive integer n for which n ? 2^k is prime for every k with 1 ≤ k ≤ log₂n. An estimate is proved for the number of such n ≤ N.     

Curvature-free upper bounds for the smallest area of a minimal surface

In this paper we will present two upper estimates for the smallest area of a possibly singular minimal surface in a closed Riemannian manifold Mⁿ with a trivial first homology group. The first upper bound will be in terms of the diameter of Mⁿ, the second estimate will be in terms of the filling radius of a manifold, leading also to the estimate in terms of the volume of Mⁿ. If n = 3 our upper bounds are for the smallest area of a smooth embedded minimal surface. After that we will establish similar upper bounds for the smallest volume of a stationary k-dimensional integral varifold in a closed Riemannian manifold Mⁿ with . The above results are the first results of such nature. Received: October 2004 Revision: May 2005 Accepted: June 2005     

Harmonic Functions,Entropy, and a Characterization of the Hyperbolic Space

Let (M ⁿ ,g) be a compact Riemannian manifold with Ric ≥−(n−1). It is well known that the bottom of spectrum λ ₀ of its universal covering satisfies λ ₀≤(n−1)²/4. We prove that equality holds iff M is hyperbolic. This follows from a sharp estimate for the Kaimanovich entropy. The author was partially supported by NSF Grant 0505645.     

On The Correlation Of Binary M-sequences

We obtain the upper bound O(2^14n/15 n^−1/5) on the number of distinct values of all possible correlation functions between M-sequences of order n .     

Number of Singularities of Stable Maps

Sharp estimates for the Ricci curvature of a submanifold M ⁿ of an arbitrary Riemannian manifold N ^n+p are established. It is shown that the equality in the lower estimate of the Ricci curvature of M ⁿ in a space form N ^n+p (c) is achieved only when M ⁿ is quasiumbilical with a flat normal bundle. In the case when the codimension p satisfies 1 ≤ p ≤ n − 3, the only submanifolds in N ^n+p (c) on which the Ricci curvature is minimal are the conformally flat ones with a flat normal bundle.      

A note on best conditioned preconditioners

We discuss the solution of Hermitian positive definite systemsAx=b by the preconditioned conjugate gradient method with a preconditionerM. In general, the smaller the condition number(M ^–1/2 AM ^–1/2 ) is, the faster the convergence rate will be. For a given unitary matrixQ, letM _Q = {Q* _N Q | _n is ann-by-n complex diagonal matrix} andM _Q ⁺ ={Q* _n Q | _n is ann-by-n positive definite diagonal matrix}. The preconditionerM _b that minimizes(M ^–1/2 AM ^–1/2 ) overM _Q ⁺ is called the best conditioned preconditioner for the matrixA overM _Q ⁺ . We prove that ifQAQ* has Young's Property A, thenM _b is nothing new but the minimizer of M –A _F overM _Q . Here · _F denotes the Frobenius norm. Some applications are also given here.     

On the limit cycles available from polynomial perturbations of the Bogdanov-Takens Hamiltonian

The displacement map related to small polynomial perturbations of the planar Hamiltonian systemdH=0 is studied in the elliptic caseH=1/2y ²+1/2x ²−1/3x ³. An estimate of the number of isolated zeros for each of the successive Melnikov functionsM _k(h),k=1, 2,…is given in terms of the orderk and the maximal degreen of the perturbation. This sets up an upper bound to the number of limit cycles emerging from the periodic orbits of the Hamiltonian system under polynomial perturbations. Research partially supported by grant MM810/98 from the NSF of Bulgaria and MURST, Italy.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

Total Scalar Curvature and L 2 Harmonic 1-Forms on a Minimal Hypersurface in Euclidean Space

Let M ⁿ , n 3, be a complete oriented immersed minimal hypersurface in Euclidean space R ⁿ⁺¹. We show that if the total scalar curvature on M is less than the n/2 power of 1/C _s , where C _s is the Sobolev constant for M, then there are no L ² harmonic 1-forms on M. As corollaries, such a minimal hypersurface contains no nontrivial harmonic functions with finite Dirichlet integral and so it has only one end. This implies finally that M is a hyperplane.     

Classification of Morse-Smale diffeomorphisms with one-dimensional set of unstable separatrices

Let M ⁿ be a closed orientable manifold of dimension n > 3. We study the class G ₁(M ⁿ ) of orientation-preserving Morse-Smale diffeomorphisms of M ⁿ such that the set of unstable separatrices of any f ∈ G ₁(M ⁿ ) is one-dimensional and does not contain heteroclinic intersections. We prove that the Peixoto graph (equipped with an automorphism) is a complete topological invariant for diffeomorphisms of class G ₁(M ⁿ ), and construct a standard representative for any class of topologically conjugate diffeomorphisms.     

Effect of the initial estimator on the asymptotic behavior of one-step M-estimator

For a general (real) parameter, let M _nbe the M-estimator and M _n ⁽¹⁾ be its one-step version (based on a suitable initial estimator M _n ⁽⁰⁾). It is known that, under certain regularity conditions, n(M _n ⁽¹⁾-M _n)=O _p(1). The asymptotic distribution of n(M _n ⁽¹⁾-M _n) is studied; it is typically non-normal and it reveals the role of the initial estimator M _n ⁽⁰⁾.Work of this author was partially supported by the Office of Naval Research, Contract No. N00014-83-K-0387     

The Maximum of a Critical Branching Wiener Process

Consider a critical branching Wiener process on ¹. Let M(n) be the location of the most right particle at time n. A limit distribution theorem is proved for n ^–1/2 M(n).     

On 4-manifolds and span-related numbers for cat manifolds

LetM ⁿ denote any closed connected CAT manifold of positive dimensionn. We define CATs(Mⁿ) to be the smallest positive dimension of all closed connected CAT manifoldsN for which the CAT span ofM×N is strictly greater than the CAT span ofN. We determine a formula for this characteristic number which involves only the Kirby-Siebenmann numberks(M) ofM and a Stiefel-Whitney number. Several results on splitting the tangent bundles of closed 4-manifolds are obtained. For example, both the Euler number ofM ⁴ andks(M⁴) represent the total obstruction to positive CAT span for a non-smoothable closed connected 4-manifold. Dedicated to the memory of Professor Otto Endler