Convergence of the shifted algorithm for unitary Hessenberg matrices

This paper shows that for unitary Hessenberg matrices the algorithm, with (an exceptional initial-value modification of) the Wilkinson shift, gives global convergence; moreover, the asymptotic rate of convergence is at least cubic, higher than that which can be shown to be quadratic only for Hermitian tridiagonal matrices, under no further assumption. A general mixed shift strategy with global convergence and cubic rates is also presented.

     

Convergence of the unitary algorithm with a unimodular Wilkinson shift

In applying the algorithm to compute the eigenvalues of a unitary Hessenberg matrix, a projected Wilkinson shift of unit modulus is proposed and proved to give global convergence with (at least) a quadratic asymptotic rate for the iteration. Experimental testing demonstrates that the unimodular shift produces more efficient numerical convergence.

     

Positive extension and completion problems for a class of structured matrices

A class of matrices, defined by a displacement rank property, is introduced. Completion and extension problems are studied for matrices in this class, under certain positivity constraints. The extension problem is reduced to a standard interpolation problem for Schur matrix valued functions.     

Positive extension and completion problems for a class of structured matrices

A class of matrices, defined by a displacement rank property, is introduced. Completion and extension problems are studied for matrices in this class, under certain positivity constraints. The extension problem is reduced to a standard interpolation problem for Schur matrix valued functions.     

Large deviation for the empirical eigenvalue density of truncated Haar unitary matrices

Let U_m be an m×m Haar unitary matrix and U_[m,n] be its n×n truncation. In this paper the large deviation is proven for the empirical eigenvalue density of U_[m,n] as m/n→λ and n→∞. The rate function and the limit distribution are given explicitly. U_[m,n] is the random matrix model of quq, where u is a Haar unitary in a finite von Neumann algebra, q is a certain projection and they are free. The limit distribution coincides with the Brown measure of the operator quq.     

A numerical comparison of two minimal residual methods for linear polynomials in unitary matrices

Two minimal residual methods for solving linear systems of the form (αU + βI)x = b, where U is a unitary matrix, are compared numerically. The first method uses conventional Krylov subspaces, while the second involves generalized Krylov subspaces. Experiments favor the second method if |α| > |β|. Moreover, the greater the ratio |α|/|β|, the higher the superiority of the second method.     

A property of eigenvalue bounds for a class of symmetric tridiagonal interval matrices

The eigenvalue bounds of interval matrices are often required in some mechanical and engineering fields. In this paper, we consider an interval eigenvalue problem with symmetric tridiagonal matrices. A theoretical result is obtained that under certain assumptions the upper and lower bounds of interval eigenvalues of the problem must be achieved just at some vertex matrices of the interval matrix. Then a sufficient condition is provided to guarantee the assumption to be satisfied. The conclusion is illustrated also by a numerical example. Copyright © 2010 John Wiley & Sons, Ltd.     

On a class of matrices generated by certain generalized permutation matrices and applications

ABSTRACT

In this paper, we study a particular class of matrices generated by generalized permutation matrices corresponding to a subgroup of some permutation group. As applications, we first present a technique from which we can get closed formulas for the roots of many families of polynomial equations with degree between 5 and 10, inclusive. Then, we describe a tool that shows how to find solutions to Fermat's last theorem and Beal's conjecture over the square integer matrices of any dimension. Finally, simple generalizations of some of the concepts in number theory to integer square matrices are presented.     

The convergence of Jacobi–Davidson iterations for Hermitian eigenproblems

Rayleigh quotient iteration is an iterative method with some attractive convergence properties for finding (interior) eigenvalues of large sparse Hermitian matrices. However, the method requires the accurate (and, hence, often expensive) solution of a linear system in every iteration step. Unfortunately, replacing the exact solution with a cheaper approximation may destroy the convergence. The (Jacobi‐) Davidson correction equation can be seen as a solution for this problem. In this paper we deduce quantitative results to support this viewpoint and we relate it to other methods. This should make some of the experimental observations in practice more quantitative in the Hermitian case. Asymptotic convergence bounds are given for fixed preconditioners and for the special case if the correction equation is solved with some fixed relative residual precision. A dynamic tolerance is proposed and some numerical illustration is presented. Copyright © 2002 John Wiley & Sons, Ltd.     

Generalization of some results concerning eigenvalues of a certain class of matrices and some applications

In this note, we present a generalization of some results concerning the spectral properties of a certain class of block matrices. As applications, we study some of its implications on nonnegative matrices and doubly stochastic matrices as well as on graph spectra and graph energy.     

Eigenvalue perturbation theory of structured real matrices and their sign characteristics under generic structured rank-one perturbations

An eigenvalue perturbation theory under rank-one perturbations is developed for classes of real matrices that are symmetric with respect to a non-degenerate bilinear form, or Hamiltonian with respect to a non-degenerate skew-symmetric form. In contrast to the case of complex matrices, the sign characteristic is a crucial feature of matrices in these classes. The behaviour of the sign characteristic under generic rank-one perturbations is analyzed in each of these two classes of matrices. Partial results are presented, but some questions remain open. Applications include boundedness and robust boundedness for solutions of structured systems of linear differential equations with respect to general perturbations as well as with respect to structured rank perturbations of the coefficients.     

The smallest eigenvalue of large Hankel matrices generated by a deformed Laguerre weight

We study the asymptotic behavior of the smallest eigenvalue, λ_N, of the Hankel (or moments) matrix denoted by , with respect to the weight . An asymptotic expression of the polynomials orthogonal with w(x) is established. Using this, we obtain the specific asymptotic formulas of λ_N in this paper. Applying a parallel numerical algorithm, we get a variety of numerical results of λ_N corresponding to our theoretical calculations.     

An inverse eigenvalue problem and a matrix approximation problem for symmetric skew-hamiltonian matrices

Based on the theory of inverse eigenvalue problem, a correction of an approximate model is discussed, which can be formulated as NX=XΛ, where X and Λ are given identified modal and eigenvalues matrices, respectively. The solvability conditions for a symmetric skew-Hamiltonian matrix N are established and an explicit expression of the solutions is derived. For any estimated matrix C of the analytical model, the best approximation matrix to minimize the Frobenius norm of C − N is provided and some numerical results are presented. A perturbation analysis of the solution is also performed, which has scarcely appeared in existing literatures. Supported by the National Natural Science Foundation of China(10571012, 10771022), the Beijing Natural Science Foundation (1062005) and the Beijing Educational Committee Foundation (KM200411232006, KM200611232010).     

Search directions for a class of projective methods

For solving linear programming problems, we describe and evaluate descent directions for projective methods in the setting of the method of de Ghellinck and Vial (1986). It is shown that choosing search directions from the projected simplex centered at 1 in transformed space guarantees a polynomial time bound. In particular, the projection of 1 coincides with the direction chosen by de Ghellinck and Vial (1986) which is well known to be equivalent to Karmarkar's search direction when the initial solution is feasible. Close to that search direction the complexity of the method is unchanged [0(nL) iterations] while in general the bound is 0(n² ·L), whereL is the size of the linear programming problem.The investigations were not made in order to improve worst case bounds, but rather to enable a free choice of search directions from a quite large class of polynomial directions. We show how different directions can be computed in one iteration using the projection of 1 with relatively small extra computational effort. In projective methods linear programming is reformulated as one-parametric feasibility problem where the parameter is the currently known upper bound on the optimal value. It is therefore very important to improve that bound whenever possible. Generalizing bounds from de Ghellinck and Vial (1986) we prove some infeasibility criteria. In particular, any computed search direction yields some upper bound which eventually improves that currently used. All bounds can be computed by solving sets of simple linear and quadratic equations.

---

Zusammenfassung Zur Lösung linearer Optimierungsaufgaben beschreiben und bewerten wir Abstiegsrichtungen bei projektiven Methoden in der Formulierung von de Ghellinck and Vial (1986). Es zeigt sich, daß bei Wahl von Suchrichtungen aus dem projizierten Simplex um 1 im transformierten Raum stets polynomiale Laufzeitabschätzungen gelten. Insbesondere die Projektion der 1 stimmt mit der von de Ghellinck and Vial (1986) gewählten Suchrichtung überein, die bekanntlich bei zulässiger Startlösung äquivalent zu Karmarkar's Suchrichtung ist. Nahe bei dieser Suchrichtung bleibt die Komplexität der Methode unverändert [0(nL) Iterationen], während im allgemeinen die Schranke 0(n² ·L) gilt, wobeiL die Größe des Linearen Optimierungsproblemes beschreibt.Die Untersuchungen zielen nicht darauf ab, Schranken für den ungünstigsten Fall zu verbessern, sondern sollen die freie Wahl von Suchrichtungen aus einer großen Klasse polynomialer Richtungen zulassen. Wir zeigen, wie man unterschiedliche Suchrichtungen innerhalb einer Iteration aus der Projektion der 1 mit relativ kleinem zusätzlichen Aufwand berechnen kann. In projektiven Methoden wird die Lineare Optimierungsaufgabe als einparametrisches Zulässigkeitsproblem reformuliert, wobei als Parameter die jeweils bekannte obere Schranke des Optimalwertes dient. Daher ist es sehr wichtig, diese Schranke bei jeder Gelegenheit zu verbessern. Durch Verallgemeinerung von Schranken aus de Ghellinck and Vial (1986) leiten wir einige Unzulässigkeitstests her. Insbesondere liefert jede berechnete Suchrichtung eine obere Schranke, die möglicherweise die bekannte obere Schranke verbessert. Alle Schranken können durch Lösung einer Reihe einfacher linearer und quadratischer Gleichungen berechnet werden.

     

The true prosoluble completion of a group: Examples and open problems

The true prosoluble completion of a group Γ is the inverse limit of the projective system of soluble quotients of Γ. Our purpose is to describe examples and to point out some natural open problems. We discuss a question of Grothendieck for profinite completions and its analogue for true prosoluble and true pronilpotent completions. Goulnara Arzhantseva and Zoran Šunić were the authors of the Appendix.     

The left and right inverse eigenvalue problems of generalized reflexive and anti-reflexive matrices

Let n×n complex matrices R and S be nontrivial generalized reflection matrices, i.e., R^∗=R=R⁻¹≠±I_n, S^∗=S=S⁻¹≠±I_n. A complex matrix A with order n is said to be a generalized reflexive (or anti-reflexive ) matrix, if RAS=A (or RAS=−A). In this paper, the solvability conditions of the left and right inverse eigenvalue problems for generalized reflexive and anti-reflexive matrices are derived, and the general solutions are also given. In addition, the associated approximation solutions in the solution sets of the above problems are provided. The results in present paper extend some recent conclusions.     

Bounds and a majorization for the real parts of the zeros of polynomials

We apply some eigenvalue inequalities to the real parts of the Frobenius companion matrices of monic polynomials to establish new bounds and a majorization for the real parts of the zeros of these polynomials.

     

The equivalence between the convergence of Ishikawa and Mann iterations with errors for strongly successively pseudocontractive mappings without Lipschitzian assumption

In this paper we prove some new equivalences between convergence of the Ishikawa and Mann iteration sequences with errors in two schemes by Xu [Y.G. Xu, Ishikawa and Mann iteration process with errors for nonlinear strongly accretive operator equations, J. Math. Anal. Appl. 224 (1998) 91-101] and Liu [L.S. Liu, Ishikawa and Mann iterative process with errors for nonlinear strongly accretive mappings in Banach spaces, J. Math. Anal. Appl. 194 (1995) 114-125], respectively, for strongly successively pseudocontractive mappings. Our main results improve and extend the corresponding results of the all references listed in this article.