Browsing by Author "Van Dooren, Paul"

Now showing 1 - 6 of 6
  • No Thumbnail Available
    Item
    Block full rank linearizations of rational matrices
    (TAYLOR & FRANCIS, 2023) Dopico, Froilán M.; Marcaida, Silvia; Quintana, María C.; Van Dooren, Paul; Department of Mathematics and Systems Analysis; Universidad Carlos III de Madrid; University of the Basque Country; Université Catholique de Louvain
    We introduce a new family of linearizations of rational matrices, which we call block full rank linearizations. The theory of block full rank linearizations is useful as it establishes very simple criteria to determine if a pencil is a linearization of a rational matrix in a target set or in the whole underlying field, by using rank conditions. Block full rank linearizations allow us to recover locally information about zeros and poles. To recover the pole-zero information at infinity, we will define the grade of the new block full rank linearizations as linearizations at infinity and the notion of degree of a rational matrix will be used. Moreover, the eigenvectors of a rational matrix associated with its eigenvalues in a target set can be obtained from the eigenvectors of its block full rank linearizations in that set. This new family of linearizations generalizes and includes the structures appearing in most of the linearizations for rational matrices constructed in the literature. As example, we study the structure and properties of the linearizations in [P. Lietaert et al., Automatic rational approximation and linearization of nonlinear eigenvalue problems, 2021].
  • Thumbnail Image
    Item
    On computing root polynomials and minimal bases of matrix pencils
    (ELSEVIER SCIENCE INC, 2023-02-01) Noferini, Vanni; Van Dooren, Paul; Department of Mathematics and Systems Analysis; Statistics and Mathematical Data Science; Algebra and Discrete Mathematics; Numerical Analysis; Université Catholique de Louvain
    We revisit the notion of root polynomials, thoroughly studied in (Dopico and Noferini, 2020 [9]) for general polynomial matrices, and show how they can efficiently be computed in the case of a matrix pencil λE+A. The method we propose makes extensive use of the staircase algorithm, which is known to compute the left and right minimal indices of the Kronecker structure of the pencil. In addition, we show here that the staircase algorithm, applied to the expansion (λ−λ0)E+(A−λ0E), constructs a block triangular pencil from which a minimal basis and a maximal set of root polynomials at the eigenvalue λ0, can be computed in an efficient manner.
  • Thumbnail Image
    Item
    Role extraction for digraphs via neighborhood pattern similarity
    (American Physical Society, 2022-11) Barbarino, Giovanni; Noferini, Vanni; Van Dooren, Paul; Department of Mathematics and Systems Analysis; Statistics and Mathematical Data Science; Algebra and Discrete Mathematics; Numerical Analysis; Université Catholique de Louvain
    We analyze the recovery of different roles in a network modeled by a directed graph, based on the so-called Neighborhood Pattern Similarity approach. Our analysis uses results from random matrix theory to show that, when assuming that the graph is generated as a particular stochastic block model with Bernoulli probability distributions for the different blocks, then the recovery is asymptotically correct when the graph has a sufficiently large dimension. Under these assumptions there is a sufficient gap between the dominant and dominated eigenvalues of the similarity matrix, which guarantees the asymptotic correct identification of the number of different roles. We also comment on the connections with the literature on stochastic block models, including the case of probabilities of order log(n)/n where n is the graph size. We provide numerical experiments to assess the effectiveness of the method when applied to practical networks of finite size.
  • Thumbnail Image
    Item
    Root vectors of polynomial and rational matrices: Theory and computation
    (ELSEVIER SCIENCE INC, 2023-01-01) Noferini, Vanni; Van Dooren, Paul; Department of Mathematics and Systems Analysis; Statistics and Mathematical Data Science; Algebra and Discrete Mathematics; Numerical Analysis; Université Catholique de Louvain
    The notion of root polynomials of a polynomial matrix P(λ) was thoroughly studied in Dopico and Noferini (2020) [6]. In this paper, we extend such a systematic approach to general rational matrices R(λ), possibly singular and possibly with coalescent pole/zero pairs. We discuss the related theory for rational matrices with coefficients in an arbitrary field. As a byproduct, we obtain sensible definitions of eigenvalues and eigenvectors of a rational matrix R(λ), without any need to assume that R(λ) has full column rank or that the eigenvalue is not also a pole. Then, we specialize to the complex field and provide a practical algorithm to compute them, based on the construction of a minimal state space realization of the rational matrix R(λ) and then using the staircase algorithm on the linearized pencil to compute the null space as well as the root polynomials in a given point λ0. If λ0 is also a pole, then it is necessary to apply a preprocessing step that removes the pole while making it possible to recover the root vectors of the original matrix: in this case, we study both the relevant theory (over a general field) and an algorithmic implementation (over the complex field), still based on minimal state space realizations.
  • Thumbnail Image
    Item
    Strongly Minimal Self-Conjugate Linearizations for Polynomial and Rational Matrices
    (SIAM PUBLICATIONS, 2022) Dopico, Froilán M.; Quintana, María C.; Van Dooren, Paul; Department of Mathematics and Systems Analysis; Universidad Carlos III de Madrid; Université Catholique de Louvain
    We prove that we can always construct strongly minimal linearizations of an arbitrary rational matrix from its Laurent expansion around the point at infinity, which happens to be the case for polynomial matrices expressed in the monomial basis. If the rational matrix has a particular self-conjugate structure, we show how to construct strongly minimal linearizations that preserve it. The structures that are considered are the Hermitian and skew-Hermitian rational matrices with respect to the real line, and the para-Hermitian and para-skew-Hermitian matrices with respect to the imaginary axis. We pay special attention to the construction of strongly minimal linearizations for the particular case of structured polynomial matrices. The proposed constructions lead to efficient numerical algorithms for constructing strongly minimal linearizations. The fact that they are valid for any rational matrix is an improvement on any other previous approach for constructing other classes of structure preserving linearizations, which are not valid for any structured rational or polynomial matrix. The use of the recent concept of strongly minimal linearization is the key for getting such generality. Strongly minimal linearizations are Rosenbrock's polynomial system matrices of the given rational matrix, but with a quadruple of linear polynomial matrices (i.e., pencils): L(λ): = [A(λ)/C(λ) -B(λ)/D(λ)], where A(λ) is regular, and the pencils [A(λ) -B(λ)] and A(λ)/C(λ)] have no finite or infinite eigenvalues. Strongly minimal linearizations contain the complete information about the zeros, poles, and minimal indices of the rational matrix and allow one to very easily recover its eigenvectors and minimal bases. Thus, they can be combined with algorithms for the generalized eigenvalue problem for computing the complete spectral information of the rational matrix.
  • No Thumbnail Available
    Item
    Structural backward stability in rational eigenvalue problems solved via block Kronecker linearizations
    (Springer, 2023-03) Dopico, Froilán M.; Quintana, María C.; Van Dooren, Paul; Universidad Carlos III de Madrid; Department of Mathematics and Systems Analysis; Université catholique de Louvain; Department of Mathematics and Systems Analysis
    In this paper we study the backward stability of running a backward stable eigenstructure solver on a pencil S(λ) that is a strong linearization of a rational matrix R(λ) expressed in the form R(λ)=D(λ)+C(λIℓ-A)-1B, where D(λ) is a polynomial matrix and C(λIℓ-A)-1B is a minimal state-space realization. We consider the family of block Kronecker linearizations of R(λ) , which have the following structure S(λ):=[M(λ)K^2TCK2T(λ)BK^1A-λIℓ0K1(λ)00],where the blocks have some specific structures. Backward stable eigenstructure solvers, such as the QZ or the staircase algorithms, applied to S(λ) will compute the exact eigenstructure of a perturbed pencil S^ (λ) : = S(λ) + ΔS(λ) and the special structure of S(λ) will be lost, including the zero blocks below the anti-diagonal. In order to link this perturbed pencil with a nearby rational matrix, we construct in this paper a strictly equivalent pencil S~ (λ) = (I- X) S^ (λ) (I- Y) that restores the original structure, and hence is a block Kronecker linearization of a perturbed rational matrix R~(λ)=D~(λ)+C~(λIℓ-A~)-1B~, where D~ (λ) is a polynomial matrix with the same degree as D(λ). Moreover, we bound appropriate norms of D~ (λ) - D(λ) , C~ - C, A~ - A and B~ - B in terms of an appropriate norm of ΔS(λ). These bounds may be, in general, inadmissibly large, but we also introduce a scaling that allows us to make them satisfactorily tiny, by making the matrices appearing in both S(λ) and R(λ) have norms bounded by 1. Thus, for this scaled representation, we prove that the staircase and the QZ algorithms compute the exact eigenstructure of a rational matrix R~ (λ) that can be expressed in exactly the same form as R(λ) with the parameters defining the representation very near to those of R(λ). This shows that this approach is backward stable in a structured sense. Several numerical experiments confirm the obtained backward stability results.