The Kronecker-canonical form of a linear pencil M - λN basically characterizes the right and left singular structure and the eigenvalue structure of the pencil. The computation of the Kronecker-canonical form may involve the use of ill-conditioned similarity transformations and, therefore, is potentially numerically unstable. Fortunately, alternative staircase forms, called Kronecker-like forms (KLFs), can be determined by employing exclusively orthogonal or unitary similarity transformations and allow to obtain basically the same (or only a part of) structural information on the pencil M - λN. Various KLFs can serve to address, in a numerically reliable way, the main applications of the Kronecker form, such as the computation of minimal left or right nullspace bases, the computation of eigenvalues and (Smith) zeros, the determination of the normal rank of polynomial and rational matrices, the computation of various factorizations of rational matrices, as well as the solution of linear equations with polynomial or rational matrices. The KLFs are also instrumental for solving computational problems in the analysis of generalized systems described by linear differential- or difference-algebraic equations (also known as descriptor systems).

A collection of functions has been implemented as a MatrixPencils.jl Julia package to compute a range of Kronecker-like forms (KLFs) which reveal the full or partial Kronecker structure of a linear pencil. The KLFs are computed by performing several pencil reduction operations on a reduced basic form of the initial pencil. These operations efficiently compress the rows or columns of certain submatrices to full rank matrices and simultaneously maintain the reduced basic form. The rank decisions involve the use of rank revealing QR-decompositions with colum pivoting or the, more reliable, SVD-decompositions. The overall computational complexity of all reduction algorithms is O(n^3), where n is the largest dimension of the pencil M - λN.

The available functions cover both real and complex numerical data. The current version of the package includes the following main functions for linear pencils:

Manipulation of general linear matrix pencils

klf                                 Computation of the Kronecker-like form exhibiting the full Kronecker structure.
klf_left                       Computation of the Kronecker-like form exhibiting the left Kronecker structure.
klf_left!                     Computation of the Kronecker-like form of a subpencil exhibiting the left Kronecker structure (overwrites input matrices)
klf_left_refine!     Separates the infinite and left Kronecker structures of a full column rank subpencil (overwrites input matrices)
klf_right                   Computation of the Kronecker-like form exhibiting the right Kronecker structure.
klf_right!                  Computation of the Kronecker-like form of a subpencil exhibiting the right Kronecker structure (overwrites input matrices)
klf_right_refine!  Separates the right and infinite Kronecker structures of a full row rank subpencil (overwrites input matrices)
klf_rlsplit                 Computation of the Kronecker-like form exhibiting the separation of right and left Kronecker structures.
preduceBF              Reduction of a pencil M - λN to the basic condensed form  [B A-λE; D C] with E upper triangular and nonsingular.

Manipulation of structured linear matrix pencils of the form [A-λE B; C D] 

sreduceBF      Reduction to the basic condensed form  [B A-λE; D C] with E upper triangular and nonsingular.
sklf                       Computation of the Kronecker-like form exhibiting the full Kronecker structure.
sklf_left             Computation of the Kronecker-like form exhibiting the left Kronecker structure.
sklf_right          Computation of the Kronecker-like form exhibiting the right Kronecker structure.                                                         
sklf_left!           Reduction of [A-λE; C-λG] , [A-λE; C]  or [A-λI; C] to a staircase form exhibiting the left Kronecker structure.
sklf_leftfin!     Reduction of [A-λE; C]  to a staircase form exhibiting the separation of its finite (unobservable) eigenvalues.
sklf_right!        Reduction of [B-λF A-λE], [B A-λE] or [B A-λI] to a staircase form exhibiting the right Kronecker structure.
sklf_rightfin!  Reduction of [B A-λE] to a staircase form exhibiting the separation of its finite (uncontrollable) eigenvalues.
gsklf             Computation of several row partition preserving special Kronecker-like forms.
 

Manipulation of regular linear matrix pencils

isregular            Checking the regularity of a pencil.
isunimodular  Checking the unimodularity of a pencil.
fisplit                    Finite-infinite eigenvalue splitting.
fisplit!                  Finite-infinite eigenvalue splitting (overwrites input matrices).
sfisplit                  Special finite-infinite eigenvalue splitting.
fihess                    Finite-infinite eigenvalue splitting in a generalized Hessenberg form
fischur                 Finite-infinite eigenvalue splitting in a generalized Schur form
fischursep         Finite-infinite eigenvalue splitting in an ordered generalized Schur form
sfischursep      Special finite-infinite eigenvalue splitting in an ordered generalized Schur form.
fiblkdiag             Finite-infinite eigenvalue splitting based block diagonalization
gsblkdiag           Finite-infinite and stable-unstable eigenvalue splitting based block diagonalization
saloc                     Spectrum alocation for the pairs (A,B) and (A-λE,B)
salocd                  Spectrum alocation for the dual pairs (A,C) and (A-λE,C)
salocinf               Infinite spectrum alocation for the pair (A-λE,B)
salocinfd            Infinite spectrum alocation for the dual pair (A-λE,C)
ordeigvals        Order-preserving computation of eigenvalues of a Schur matrix or a generalized Schur pair.
_qrE!                     Reduce the regular pencil A-λE to an equivalent form with E upper triangular.
_svdlikeAE!      Reduce the regular pencil A-λE to an equivalent rank-revealing SVD-like form with E upper triangular or diagonal.
 

Some applications of matrix pencil computations

pkstruct   Determination of the Kronecker structure information.
prank         Determination of the normal rank.
peigvals    Computation of the finite and infinite eigenvalues.
pzeros        Computation of the finite and infinite (Smith) zeros.
 

Some applications of structured linear matrix pencils of the form [A-λE B; C D]

spkstruct   Determination of the Kronecker structure information.
sprank         Determination of the normal rank.
speigvals   Computation of the finite and infinite eigenvalues.
spzeros       Computation of the finite and infinite (Smith) zeros.
 

Manipulation of linearizations of the form [A-λE B; C D] and [A-λE B-λF; C-λG D-λH]

lsminreal      Computation of minimal order linearizations [A-λE B; C D] of rational matrices.
lsminreal2   Computation of minimal order linearizations [A-λE B; C D] of rational matrices (potentially more efficient).
lpsminreal   Computation of minimal order pencil based linearizations [A-λE B-λF; C-λG D-λH] of rational matrices.
lsequal           Checking the equivalence of two linearizations.
lpsequal        Checking the equivalence of two pencil based linearizations.
lseval              Evaluation of the value of the rational matrix corresponding to a descriptor system based linearization.
lpseval           Evaluation of the value of the rational matrix corresponding to a pencil based linearization.
lps2ls              Conversion of a pencil based linearization into a descriptor system based linearization.
lsbalance!    Scaling of descriptor system based linearizations.
lsbalqual      Evaluation of the scaling quality of  descriptor system based linearizations. 

The implementations of above functions rely on a set of low level functions for manipulating subpencils:

Operations on general linear matrix pencils

_preduceBF!   Reduction of a subpencil M - λN to the basic condensed form  [B A-λE; D C] with E upper triangular and nonsingular.
_preduce1!     Row compression of [B; D] with preservation of the upper triangular form of E.
_preduce2!     Row compression of B with preservation of the upper triangular form of E.
_preduce3!     Column compression of [D C] with preservation of the upper triangular form of E.
_preduce4!     Column compression of C with preservation of the upper triangular form of E.

Operations on structured linear matrix pencils

_sreduceB!           Row compression of B by applying an orthogonal transformation from left to the matrices B, A and E.
_sreduceBA!       Row compression of B by applying an orthogonal similarity transformation to the triple (A, B, C).
_sreduceBAE!    Row compression of B by applying an orthogonal similarity transformation to the triple (A-λE, B, C).
_sreduceC!          Column compression of C by applying an orthogonal transformations from right to the matrices C, A and E.
_sreduceAC!       Column compression of C by applying an orthogonal simlarity transformation to the triple (A, B, C).
_sreduceAEC!   Column compression of C by applying an orthogonal simlarity transformation to the triple (A-λE, B, C).

Important applications of linear pencils is the manipulation of polynomial and rational matrices using suitable linearizations. The current version of the package includes the following functions for polynomial and rational matrices: 

Manipulation of polynomial matrices

poly2pm       Conversion of a polynomial matrix from the Polynomials package format to a 3D matrix.
pm2poly       Conversion of a polynomial matrix from a 3D matrix to the Polynomials package format.
pmdeg            Determination of the degree of a polynomial matrix.
pmeval           Evaluation of a polynomial matrix for a given value of its argument.
pmreverse   Building the reversal of a polynomial matrix.
pmdivrem   Quotients and remainders of elementwise divisions of two polynomial matrices.
pm2lpCF1   Building a linearization in the first companion Frobenius form.
pm2lpCF2   Building a linearization in the second companion Frobenius form.
pm2ls             Building a structured linearization of a polynomial matrix.
ls2pm            Computation of the polynomial matrix from its structured linearization.
pm2lps         Building a linear pencil based structured linearization of a polynomial matrix.
lps2pm        Computation of the polynomial matrix from its linear pencil based structured linearization.
spm2ls         Building a structured linearization [A-λE B; C D] of a structured polynomial matrix [T(λ) U(λ); V(λ) W(λ)].
spm2lps      Building a linear pencil based structured linearization [A-λE B-λF; C-λG D-λH] of a structured polynomial matrix [T(λ) U(λ); V(λ) W(λ)].

Some applications to polynomial matrices

pmkstruct               Determination of the Kronecker structure and infinite pole-zero structure.
pmeigvals                Computation of the finite and infinite eigenvalues.
pmzeros                    Computation of the finite and infinite zeros.
pmzeros1                 Computation of the finite and infinite zeros using linear pencil based structured linearization.
pmzeros2                 Computation of the finite and infinite zeros using structured pencil based linearization.
pmroots                     Computation of the roots of the determinant of a regular polynomial matrix.
pmpoles                     Computation of the infinite poles.
pmpoles1                  Computation of the infinite poles using linear pencil based structured linearization.
pmpoles2                  Computation of the infinite poles using structured pencil based linearization.
pmrank                       Determination of the normal rank.
ispmregular             Checking the regularity of a polynomial matrix.
ispmunimodular   Checking the unimodularity of a polynomial matrix.

Manipulation of rational matrices

rm2lspm     Representation of a rational matrix as a linearization of its strictly proper part plus its polynomial part.
rmeval         Evaluation of a rational matrix for a given value of its argument.
rm2ls            Building a descriptor system based structured linearization of a rational matrix.
ls2rm            Computation of the rational matrix from its descriptor system based structured linearization.
rm2lps          Building a pencil based structured linearization of a rational matrix.
lps2rm          Computation of the rational matrix from its pencil based structured linearization.
lpmfd2ls      Building a descriptor system based structured linearization of a left polynomial matrix fractional description.
rpmfd2ls      Building a descriptor system based structured linearization of a right polynomial matrix fractional description.
lpmfd2lps    Building a pencil based structured linearization of a left polynomial matrix fractional description.
rpmfd2lps   Building a pencil based structured linearization of a right polynomial matrix fractional description.
pminv2ls      Building a descriptor system based structured linearization of the inverse of a polynomial matrix.
pminv2lps    Building a pencil based structured linearization of the inverse of a polynomial matrix.

Some applications to rational matrices

rmkstruct   Determination of the Kronecker structure and infinite pole-zero structure.
rmzeros       Computation of the finite and infinite zeros using structured pencil based linearization.
rmzeros1    Computation of the finite and infinite zeros using linear pencil based structured linearization.
rmpoles       Computation of the infinite poles using structured pencil based linearization.
rmpoles1    Computation of the infinite poles using linear pencil based structured linearization.
rmrank         Determination of the normal rank.

The implementations of the functions for the manipulation of polynomial and rational matrices rely on a set of low level functions for manipulating polynomials:

Manipulation of polynomials

poldeg             Degree of a polynomial.
poldeg1          Degree of a polynomial plus one.
conv                  Convolution of two vectors (or product of two polynomials).
convmtx         Building the convolution matrix for a given vector.
poldivrem      Quotient and remainder of the division of two polynomials.
poldiv                Quotient of the exact division of two polynomials.
polgcdvw        Greatest common divisor of two polynomials.
gcdvwupd      Iterative refinement of the accuracy of the greatest common divisor of two polynomials.
pollcm              Least common multiple of two polynomials.
polcoeffval   Coefficients of a polynomial from its roots and the value of the polynomial in a point.
qrsolve!          Fast least-squares solver for full column rank Hessenberg-like matrices.