Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion

We describe randomized algorithms for computing the dominant eigenmodes of the generalized Hermitian eigenvalue problem Ax = λBx, with A Hermitian and B Hermitian and positive definite. The algorithms we describe only require forming operations Ax,Bx and B^?1x and avoid forming square roots of B (or operations of the form, B^1/2x or B^?1/2x). We provide a convergence analysis and a posteriori error bounds and derive some new results that provide insight into the accuracy of the eigenvalue calculations. The error analysis shows that the randomized algorithm is most accurate when the generalized singular values of B^?1A decay rapidly. A randomized algorithm for the generalized singular value decomposition is also provided. Finally, we demonstrate the performance of our algorithm on computing an approximation to the Karhunen–Loève expansion, which involves a computationally intensive generalized Hermitian eigenvalue problem with rapidly decaying eigenvalues. Copyright © 2015 John Wiley & Sons, Ltd.     

Geronimus spectral transforms and measures on the complex plane

We analyze a special spectral transform of a measure μ supported on a compact subset C of the complex plane. A perturbation μ₁ of μ is said to be a Geronimus spectral transform if where αC. We focus our attention in the analysis of the Hessenberg matrix associated with the multiplication operator in terms of the orthogonal polynomial basis defined by the measure μ₁.     

On the multiplicity of the eigenvalues of a graph

Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q ₁(t)q ₂(t)² ... q _m (t)^m, where each q _i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q _j (t). We give an algorithm to construct the polynomials q _i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λ_i| of G, where λ₁, λ₂, ..., λ_n are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.     

On the intersection of Hermitian curves and of Hermitian surfaces

Kestenband [Unital intersections in finite projective planes, Geom. Dedicata 11(1) (1981) 107–117; Degenerate unital intersections in finite projective planes, Geom. Dedicata 13(1) (1982) 101–106] determines the structure of the intersection of two Hermitian curves of PG(2,q²), degenerate or not. In this paper we give a new proof of Kestenband's results. Giuzzi [Hermitian varieties over finite field, Ph.D. Thesis, University of Sussex, 2001] determines the structure of the intersection of two non-degenerate Hermitian surfaces and of PG(3,q²) when the Hermitian pencil defined by and contains at least one degenerate Hermitian surface. We give a new proof of Giuzzi's results and we obtain some new results in the open case when all the Hermitian surfaces of the Hermitian pencil are non-degenerate.     

LDPC codes from the Hermitian curve

In this paper, we study the code which has as parity check matrix the incidence matrix of the design of the Hermitian curve and its (q + 1)-secants. This code is known to have good performance with an iterative decoding algorithm, as shown by Johnson and Weller in (Proceedings at the ICEE Globe com conference, Sanfrancisco, CA, 2003). We shall prove that has a double cyclic structure and that by shortening in a suitable way it is possible to obtain new codes which have higher code-rate. We shall also present a simple way to constructing the matrix via a geometric approach.      

On self-orthogonal group ring codes

We obtain structural results about group ring codes over F[G], where F is a finite field of characteristic p > 0 and the Sylow p-subgroup of the Abelian group G is cyclic. As a special case, we characterize cyclic codes over finite fields in the case the length of the code is divisible by the characteristic of the field. By the same approach we study cyclic codes of length m over the ring R = F _q [u], u ^r  = 0 with r  > 0, gcd(m, q) = 1. Finally, we give a construction of quasi-cyclic codes over finite fields.      

Hermitian decomposition of continuous functions on a fractal surface

In this paper the Théodoresco transform is used to show that, under additional assumptions, each Hölder continuous function f defined on the boundary Γ of a fractal domain Ω ? ?²ⁿ can be expressed as f = Ψ⁺ ? Ψ^?, where Ψ^± are Hölder continuous functions on Γ and Hermitian monogenically extendable to Ω and to ?²ⁿ ? (Ω ∪ Γ) respectively.     

Symmetrization of diagonalizable complex differential systems

Let L be a first order system where D₀=∂/∂x₀, Dj=∂/∂xj, y is a real vector parameter, I is the idendity 3×3 matrix and aj(y) is a 3×3 matrix-valued complex smooth function.Let L(y,ξ) be the symbol of L(y,D). We assume: ∀y, the real reduced dimension of L in y is 5 and L(y,ξ) is symmetrizable: ∃T(y) such that: T−1(y)L(y,ξ)T(y) is hermitian ∀ξ. We assume the nonexistence of some double characteristics depending on the reduced form of the system. Then: L(y,ξ) is smoothly symmetrizable ? ∃T(y) smooth (same smoothness as the coefficients) such that: T−1(y)L(y,ξ)T(y) is hermitian ∀ξ.     

Weyl and Lidski? Inequalities for General Hyperbolic Polynomials

The roots of hyperbolic polynomials satisfy the linear inequalities that were previously established for the eigenvalues of Hermitian matrices, after a conjecture by A. Horn. Among them are the so-called Weyl and Lidskiǐ inequalities. An elementary proof of the latter for hyperbolic polynomials is given. This proof follows an idea from H. Weinberger and is free from representation theory and Schubert calculus arguments, as well as from hyperbolic partial differential equations theory.