To solving spectral problems for multiparameter polynomial matrices

An approach to solving spectral problems for multiparameter polynomial matrices based on passing to accompanying pencils of matrices is described. Also reduction of spectral problems for multiparameter pencils of complex matrices to the corresponding real problems is considered. Bibliography: 6 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2006, pp. 212–231.     

Solution of spectral problems for polynomial matrices

For polynomial matrices of full rank, including matrices of the form A - I and A - B, numerical methods for solving the following problems are suggested: find the divisors of a polynomial matrix whose spectra coincide with the zeros of known divisors of its characteristic polynomial; compute the greatest common divisor of a sequence of polynomial matrices; solve the inverse eigenvalue problem for a polynomial matrix. The methods proposed are based on the W and V factorizations of polynomial matrices. Applications of these methods to the solution of certain algebraic problems are considered. Bibliography: 3 titles._________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 296, 2003, pp. 122–138.     

Spectral problems for pencils of polynomial matrices. Methods and algorithms. V

Methods and algorithms for the solution of spectral problems of singular and regular pencils D(λ, μ)=A(μ)-λB(μ) of polynomial matrices A(μ) and B(μ) are suggested (the separation of continuous and discrete spectra, the computation of points of a discrete spectrum with the corresponding, Jordan chains, the computation of minimal indices and a minimal basis of polynomial solutions, the computation of the determinant of a regular pencil). Bibliography: 13 titles. Translated by V. N. Kublanovskaya Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 26–70     

Inversion of polynomial and rational matrices

The inversion of polynomial and rational matrices is considered. For regular matrices, three algorithms for computing the inverse matrix in a factored form are proposed. For singular matrices, algorithms of constructing pseudoinverse matrices are considered. The algorithms of inversion of rational matrices are based on the minimal factorization which reduces the problem to the inversion of polynomial matrices. A class of special polynomial matrices is regarded whose inverse matrices are also polynomial matrices. Inversion algorithms are applied to the solution of systems with polynomial and rational matrices. Bibliography: 3 titles. Translated by V. N. Kublanovskaya. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 97–109.     

Methods for solving spectral problems for multiparameter matrix pencils

Methods for solving the partial eigenproblem for multiparameter regular pencils of real matrices, which allow one to improve given approximations of an eigenvector and the associated point of the spectrum (both finite and infinite) are suggested. Ways of extending the methods to complex matrices, polynomial matrices, and coupled multiparameter problems are indicated. Bibliography: 10 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 296, 2003, pp. 139–168.     

Differentiation of generalized inverses for rational and polynomial matrices

Our basic motivation is a direct method for computing the gradient of the pseudo-inverse of well-conditioned system with respect to a scalar, proposed in [13] by Layton. In the present paper we combine the Layton’s method together with the representation of the Moore-Penrose inverse of one-variable polynomial matrix from [24] and developed an algorithm for computing the gradient of the Moore-Penrose inverse for one-variable polynomial matrix. Moreover, using the representation of various types of pseudo-inverses from [26], based on the Grevile’s partitioning method, we derive more general algorithms for computing {1}, {1, 3} and {1, 4} inverses of one-variable rational and polynomial matrices. Introduced algorithms are implemented in the programming language MATHEMATICA. Illustrative examples on analytical matrices are presented.     

To solving spectral problems for <Emphasis Type="Italic">q</Emphasis>-parameter polynomial matrices

The method of hereditary pencils, originally suggested by the author for solving spectral problems for two-parameter matrices (pencils of matrices), is extended to the case of q-parameter, q ≥ 2, polynomial matrices. Algorithms for computing points of the finite regular and singular spectra of a q-parameter polynomial matrix and their theoretical justification are presented. Bibliography: 2 titles.     

A rational spectral collocation method for solving a class of parameterized singular perturbation problems

A new kind of numerical method based on rational spectral collocation with the sinh transformation is presented for solving parameterized singularly perturbed two-point boundary value problems with one boundary layer. By means of the sinh transformation, the original Chebyshev points are mapped onto the transformed ones clustered near the singular points of the problem. The results from asymptotic analysis as regards the singularity of the solution are employed to determine the parameters in the transformation. Numerical experiments including several nonlinear cases illustrate the high accuracy and efficiency of our method.     

To solving multiparameter problems of algebra. 6. Spectral characteristics of polynomial matrices

For a q-parameter polynomial m × n matrix F of rank ρ, solutions of the equation Fx = 0 at points of the spectrum of the matrix F determined by the (q −1)-dimensional solutions of the system Z[F] = 0 are considered. Here, Z[F] is the polynomial vector whose components are all possible minors of order ρ of the matrix F. A classification of spectral pairs in terms of the matrix A[F], with which the vector Z[F] is associated, is suggested. For matrices F of full rank, a classification and properties of spectral pairs in terms of the so-called levels of heredity of points of the spectrum of F are also presented. Bibliography: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 132–149.     

On spectral properties of multiparameter polynomial matrices

Spectral problems for multiparameter polynomial matrices are considered. The notions of the spectrum (including those of its finite, infinite, regular, and singular parts), of the analytic multiplicity of a point of the spectrum, of bases of null-spaces, of Jordan s-semilattices of vectors and of generating vectors, and of the geometric and complete geometric multiplicities of a point of the spectrum are introduced. The properties of the above characteristics are described. A method for linearizing a polynomial matrix (with respect to one or several parameters) by passing to the accompanying pencils is suggested. The interrelations between spectral characteristics of a polynomial matrix and those of the accompanying pencils are established. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 284–321. Translated by V. B. Khazanov.     

Modified extragradient algorithms for solving equilibrium problems

ABSTRACT

In this paper, we introduce some new algorithms for solving the equilibrium problem in a Hilbert space which are constructed around the proximal-like mapping and inertial effect. Also, some convergence theorems of the algorithms are established under mild conditions. Finally, several experiments are performed to show the computational efficiency and the advantage of the proposed algorithm over other well-known algorithms.     

Memetic algorithms for solving job-shop scheduling problems

The job-shop scheduling problem is well known for its complexity as an NP-hard problem. We have considered JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. In this paper, we developed a memetic algorithm (MA) for solving JSSPs. Three priority rules were designed, namely partial re-ordering, gap reduction and restricted swapping, and used as local search techniques in our MA. We have solved 40 benchmark problems and compared the results obtained with a number of established algorithms in the literature. The experimental results show that MA, as compared to GA, not only improves the quality of solutions but also reduces the overall computational time.     

The eigenvalues of Hermite and rational spectral differentiation matrices

Summary We derive expressions for the eigenvalues of spectral differentiation matrices for unbounded domains. In particular, we consider Galerkin and collocation methods based on Hermite functions as well as rational functions (a Fourier series combined with a cotangent mapping). We show that (i) first derivative matrices have purely imaginary eigenvalues and second derivative matrices have real and negative eigenvalues, (ii) for the Hermite method the eigenvalues are determined by the roots of the Hermite polynomials and for the rational method they are determined by the Laguerre polynomials, and (iii) the Hermite method has attractive stability properties in the sense of small condition numbers and spectral radii.     

Building and solving matrix spectral problems

When an infinite dimensional operator T: X → X is approximated with (a slight perturbation of) an operator T_n : X → X of finite rank less than or equal to n, the spectral elements of an auxiliary matrix Z ∈ ℂ^{n ×n} , lead to those of Tn, if they are computed exactly. This contribution covers a general theoretical framework for matrix problems issued from finite rank discretizations and perturbed variants, the stop criterion of the QR method for eigenvalues, the possibility of using the Newton method to compute a Schur form, and the use of Newton method to refine coarse approximate bases of spectral subspaces. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Extensions of Faddeev’s algorithms to polynomial matrices

Starting from algorithms introduced in [Ky M. Vu, An extension of the Faddeev’s algorithms, in: Proceedings of the IEEE Multi-conference on Systems and Control on September 3-5th, 2008, San Antonio, TX] which are applicable to one-variable regular polynomial matrices, we introduce two dual extensions of the Faddeev’s algorithm to one-variable rectangular or singular matrices. Corresponding algorithms for symbolic computing the Drazin and the Moore-Penrose inverse are introduced. These algorithms are alternative with respect to previous representations of the Moore-Penrose and the Drazin inverse of one-variable polynomial matrices based on the Leverrier-Faddeev’s algorithm. Complexity analysis is performed. Algorithms are implemented in the symbolic computational package MATHEMATICA and illustrative test examples are presented.