Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation

Summary. We study the role of preconditioning strategies recently developed for coercive problems in connection with a two-step iterative method, based on the Hermitian skew-Hermitian splitting (HSS) of the coefficient matrix, proposed by Bai, Golub and Ng for the solution of nonsymmetric linear systems whose real part is coercive. As a model problem we consider Finite Differences (FD) matrix sequences {A_n(a,p)}_n discretizing the elliptic (convection-diffusion) problem with being a plurirectangle of R^d with a(x) being a uniformly positive function and p(x) denoting the Reynolds function: here for plurirectangle we mean a connected union of rectangles in d dimensions with edges parallel to the axes. More precisely, in connection with preconditioned HSS/GMRES like methods, we consider the preconditioning sequence {P_n(a)}_n, P_n(a):= D_n^1/2(a)A_n(1,0) D_n^1/2(a) where D_n(a) is the suitably scaled main diagonal of A_n(a,0). If a(x) is positive and regular enough, then the preconditioned sequence shows a strong clustering at unity so that the sequence {P_n(a)}_n turns out to be a superlinear preconditioning sequence for {A_n(a,0)}_n where A_n(a,0) represents a good approximation of Re(A_n(a,p)) namely the real part of A_n(a,p). The computational interest is due to the fact that the preconditioned HSS method has a convergence behavior depending on the spectral properties of {P_n^-1(a)Re(A_n(a,p))}_n {P_n^-1(a)A_n(a,0)}_n: therefore the solution of a linear system with coefficient matrix A_n(a,p) is reduced to computations involving diagonals and to the use of fast Poisson solvers for {A_n(1,0)}_n.Some numerical experimentations confirm the optimality of the discussed proposal and its superiority with respect to existing techniques.Mathematics Subject Classification (1991): 65F10, 65N22, 15A18, 15A12, 47B65     

On Some Optimal Constructions of Chess Tournament Combinations

An optimal solution for the following “chess tournament” problem is given. Let n, r be positive integers such that r<n. Put N=2n, R=2r+1. Let X_N,R be the set of all ordered pairs (T, A) of matrices of degree N such that T=(t_ij) is symmetric, A=(a_ij) is skew-symmetric, t_ij ∈,{0, 1, 2,…, R), a_ij ∈{0,1,–1}. Moreover, suppose t_ii=a_ii=0 (1?i?N). t_ij = t_ik>0 implies j=k, t_ij=0 is equivalent to a_ij=0, and |a_i1|+|a_i2|+…+|a_iN|=R (1?i?N). Let p(T, A) be the number of i such that 1?i?N and a_i1 + a_i2 + … + a_iN >0. The main result of this note is to show that max p(T, A) for (T, A)∈X_{N, R} is equal to [n(2r+1)/(r+1)], and a pair (T₀, A₀) satisfying p(T₀, A₀)=[n(2r+1)/(r+1)] is also given.     

Operator algebras and a theorem of Dieudonne

LetA be aC*-algebra with second dualA″. Let (φ _n)(n=1,...) be a sequence in the dual ofA such that limφ _n(a) exists for eacha εA. In general, this does not imply that limφ _n(x) exists for eachx εA″. But if limφ _n(p) exists whenever p is the range projection of a positive self-adjoint element of the unit ball ofA, then it is shown that limφ _n(x) does exist for eachx inA″. This is a non-commutative generalisation of a celebrated theorem of Dieudonné. A new proof of Dieudonné’s theorem, for positive measures, is given here. The proof of the main result makes use of Dieudonné’s original theorem.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

The additive subgroup generated by a polynomial

SupposeR is a prime ring with the centerZ and the extended centroidC. Letp(x ₁, …,x _n) be a polynomial overC in noncommuting variablesx ₁, …,x _n. LetI be a nonzero ideal ofR andA be the additive subgroup ofRC generated by {p(a ₁, …,a _n):a ₁, …,a _n ∈I}. Then eitherp(x ₁, …,x _n) is central valued orA contains a noncentral Lie ideal ofR except in the only one case whereR is the ring of all 2 × 2 matrices over GF(2), the integers mod 2.     

Almost all trees share a complete set of immanantal polynomials

Let χ be an irreducible character of the symmetric group S_n. For an n-by-n matrix A = (a_ij), define If G is a graph, let D(G) be the diagonal matrix of its vertex degrees and A(G) its adjacency matrix. Let y and z be independent indeterminates, and define L(G) = yD(G) + zA(G). Suppose t_n is the number of trees on n vertices and s_n is the number of such trees T for which there exists a nonisomorphic tree T? such that d_χ(xl - L(T)) = d_x(xl - L(T?)) for every irreducible character χ of S_n. Then lim_n→∞ S_n/t_n = 1. © 1993 John Wiley & Sons, Inc.     

Minimum permanents of doubly stochastic matrices with One fixed entry

For n  3 and sufficiently small a  0, the minimum value of the permanent function restricted on n × n doubly stochastic matrices with at least one entry equal to a is obtained. For n = 3, the explicit form of the function p is derived where p(a) = min{per(C):C = (c_ij )?Ω₃ c ₁₁ = a}a? [0, 1].     

Analytic properties of conditional curvatures of convex hypersurfaces and the dirichlet problem for the Monge-Ampère equation

The existence and uniqueness of a surface with given geometric characteristics is one of the important topical problems of global differential geometry. By stating this problem in terms of analysis, we arrive at second-order elliptic and parabolic partial differential equations. In the present paper we consider generalized solutions of the Monge-Ampère equation ||z _ij || = ϕ(x, z, p) in Λ ⁿ , wherez = z(x ₁,...,z _n ) is a convex function,p = (p ₁,...,P _n) = (∂z/∂x ₁,...,ϖz/ϖx _n), andz _ij =ϖ ² z/ϖx _i ϖx _j. We consider the Cayley-Klein model of the space Λ ⁿ and use a method based on fixed point principle for Banach spaces. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 763–768, November, 1998.     

On the solutions to x′(t) = A(t) x (t) over all A(t), where P ⩽ A(t) ⩽ Q

Let P_ij and q_ij be positive numbers for i ≠ j, i, j = 1, …, n, and consider the set of matrix differential equations x′(t) = A(t) x(t) over all A(t), where a_ij(t) is piecewise continuous, a_ij(t) = ?∑_{i ≠ j}a_ij(t), and p_ij ? a_ij(t) ? q_ij all t. A solution x is also to satisfy ∑_{i = 1}ⁿx_i(0) = 1. Let C_t denote the set of all solutions, evaluated at t to equations described above. It is shown that $\text{C}{}_{\mathrm{t}}$, the topological closure of C_t, is a compact convex set for each t. Further, the set valued function $\text{C}{}_{\mathrm{t}}$, of t is continuous and $\text{limit}{}_{\mathrm{t\; \to \; \infty }}\text{C}\text{?}{}_{\mathrm{t}}\text{= ∩}\text{C}\text{?}{}_{\mathrm{t}}$.     

Spherical Maximal Operators on Radial Functions

Let A_tf(x) denote the mean of f over a sphere of radius t and center x. We prove sharp estimates for the maximal function M_E f(X) = sup_t∈_E |Atf(x)| where E is a fixed set in IR⁺ and f is a radial function ∈ L^p(IR^d). Let P_d = d/(d?1) (the critical exponent for Stein's maximal function). For the cases (i) p < p_d, d ? 2, and (ii) p = p_d, d ? 3, and for p ? q ? ∞ we prove necessary and sufficient conditions on E for M_E to map radial functions in L^p to the Lorentz space L^P,q.     

On Strong Versions of the Central Limit Theorem

Let S_n be the sum of n i.i.d.r.v. and let 1_(-∞,x)(·) be the indicator function of the interval (-∞, x). Then the sequence 1_{(-∞, x)}(S_n/√n) does not converge for any x. Likewise the arithmetic means of this sequence converge only with probability zero. But the logarithmic means converge with probability one to the standard normal distribution Ø(x). Then for any bounded and a.e. continuous function a(y) the logarithmic means of a(S_n/√n) converge a.s. to a = ∫a(y)dØ(y). The arithmetic means of a(S_nk/√n) converge to the same limit a for all subsequences n_k = [c^k], c > 1.     

How often can a given distance occur in a finite set of integers?

Let n, a, d be natural numbers and A a set of integers of the closed interval [0, n] with | A | = a. Then we establish sharp lower and upper bounds for the number of pairs (x,y) ? A×A(x,y)\in A\times A for which y - x = d. Roughly spoken, we investigate how often a distance d can occur in A.     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

A large-deviation result for the range of random walk and for the Wiener sausage

Let {S _n } be a random walk on ℤ ^d and let R _n be the number of different points among 0, S ₁,…, S _{n −1}. We prove here that if d≥ 2, then ψ(x) := lim _{n →∞}(−:1/n) logP{R _n ≥nx} exists for x≥ 0 and establish some convexity and monotonicity properties of ψ(x). The one-dimensional case will be treated in a separate paper. We also prove a similar result for the Wiener sausage (with drift). Let B(t) be a d-dimensional Brownian motion with constant drift, and for a bounded set A⊂ℝ ^d let Λ _t = Λ _t (A) be the d-dimensional Lebesgue measure of the `sausage' ∪_{0≤ s ≤ t} (B(s) + A). Then φ(x) := lim _t→∞: (−1/t) log P{Λ _t ≥tx exists for x≥ 0 and has similar properties as ψ. Received: 20 April 2000 / Revised version: 1 September 2000 / Published online: 26 April 2001     

Inequalities and identities for generalized matrix functions

Let χ be a character on the symmetric group S_n, and let A = (a_ij) be an n-by-n matrix. The function d_χ(A) = Σ_σ?Snχ(σ)Πⁿ_{t = 1}a_tσ(t) is called a generalized matrix function. If χ is an irreducible character, then d_χ is called an immanent. For example, if χ is the alternating character, then d_χ is the determinant, and if χ ≡ 1, then d_χ is called the permanent (denoted per). Suppose that A is positive semidefinite Hermitian. We prove that the inequality $\text{(1/χ(}\text{id}\text{))d}{}_{\mathrm{\chi }}\text{(A) ?}\text{per}\text{A}$ holds for a variety of characters χ including the irreducible ones corresponding to the partitions (n ? 1,1) and (n ? 2,1,1) of n. The main technique used to prove these inequalities is to express the immanents as sums of products of principal subpermanents. These expressions for the immanents come from analogous expressions for Schur polynomials by means of a correspondence of D.E. Littlewood.     

One-Sided Ideal Growth of Free Associative Algebras

Let R be a finitely generated associative algebra with unity over a finite field \Bbb F_q{\Bbb F}_q . Denote by a _n (R) the number of left ideals J ⊂ R such that dim R/J = n for all n ≥ 1. We explicitly compute and find asymptotics of the left ideal growth for the free associative algebra A _d of rank d with unity over \Bbb F_q{\Bbb F}_q , where d ≥ 1. This function yields a bound a _n (R) ≤ a _n (A _d ), n ? \Bbb Nn\in{\Bbb N} , where R is an arbitrary algebra generated by d elements. Denote by m _n (R) the number of maximal left ideals J ⊂ R such that dim R/J = n, for n ≥ 1. Let d ≥ 2, we prove that m _n (A _d ) ≈ a _n (A _d ) as n → ∞.     

Adjacency preserving functions on symmetric elements and linear preservers of non-zero decomposable symmetric tensors

Let A be a non-empty set and m be a positive integer. Let ≡ be the equivalence relation defined on A ^m such that (x ₁, …, x _m ) ≡ (y ₁, …, y _m ) if there exists a permutation σ on {1, …, m} such that y _σ(i) = x _i for all i. Let A ^(m) denote the set of all equivalence classes determined by ≡. Two elements X and Y in A ^(m) are said to be adjacent if (x ₁, …, x _m?1, a) ∈ X and (x ₁, …, x _m?1, b) ∈ Y for some x ₁, …, x _m?1 ∈ A and some distinct elements a, b ∈ A. We study the structure of functions from A ^(m) to B ⁽ⁿ⁾ that send adjacent elements to adjacent elements when A has at least n + 2 elements and its application to linear preservers of non-zero decomposable symmetric tensors.