Basic reductions of general and structured linear matrix pencils
MatrixPencils._preduceBF! — Function_preduceBF!(M, N, Q, Z, L::Union{AbstractMatrix,Missing}, R::Union{AbstractMatrix,Missing};
fast = true, atol = 0, rtol, roff = 0, coff = 0, rtrail = 0, ctrail = 0,
withQ = true, withZ = true) -> n, m, pReduce the partitioned matrix pencil M - λN
[ * * * ] roff
M - λN = [ 0 M22-λN22 * ] npp
[ 0 0 * ] rtrail
coff npm ctrailto an equivalent basic form F - λG = Q1'*(M - λN)*Z1 using orthogonal transformation matrices Q1 and Z1 such that the subpencil M22 - λN22 is transformed into the following standard form
| B | A-λE |
F22 - λG22 = |----|------| ,
| D | C |where E is an nxn non-singular matrix, and A, B, C, D are nxn-, nxm-, pxn- and pxm-dimensional matrices, respectively. The order n of E is equal to the numerical rank of N determined using the absolute tolerance atol and relative tolerance rtol. M and N are overwritten by F and G, respectively.
The performed orthogonal or unitary transformations are accumulated in Q (i.e., Q <- Q*Q1), if withQ = true, and Z (i.e., Z <- Z*Z1), if withZ = true.
The matrix L is overwritten by Q1'*L unless L = missing and the matrix R is overwritten by R*Z1 unless R = missing.
If fast = true, E is determined upper triangular using a rank revealing QR-decomposition with column pivoting of N22 and n is evaluated as the number of nonzero diagonal elements of the R factor, whose magnitudes are greater than tol = max(atol,abs(R[1,1])*rtol). If fast = false, E is determined diagonal using a rank revealing SVD-decomposition of N22 and n is evaluated as the number of singular values greater than tol = max(atol,smax*rtol), where smax is the largest singular value. The rank decision based on the SVD-decomposition is generally more reliable, but the involved computational effort is higher.
MatrixPencils._preduce1! — Function_preduce1!(n::Int, m::Int, p::Int, M::AbstractMatrix, N::AbstractMatrix,
Q::Union{AbstractMatrix,Nothing}, Z::Union{AbstractMatrix,Nothing}, tol,
L::Union{AbstractMatrix{T},Missing} = missing, R::Union{AbstractMatrix{T},Missing} = missing;
fast = true, roff = 0, coff = 0, rtrail = 0, ctrail = 0, withQ = true, withZ = true)Reduce the structured pencil M - λN
M = [ * * * * ] roff N = [ * * * * ] roff
[ 0 B A * ] n [ 0 0 E * ] n
[ 0 D C * ] p [ 0 0 0 * ] p
[ 0 * * * ] rtrail [ 0 * * * ] rtrail
coff m n ctrail coff m n ctrailwith E upper triangular and nonsingular to the following form M1 - λN1 = Q1'*(M - λN)*Z1 with
M1 = [ * * * * * ] roff N1 = [ * * * * * ] roff
[ 0 B1 A11 A12 * ] τ+ρ [ 0 0 E11 E12 * ] τ+ρ
[ 0 0 B2 A22 * ] n-ρ [ 0 0 0 E22 * ] n-ρ
[ 0 0 D2 C2 * ] p-τ [ 0 0 0 0 * ] p-τ
[ 0 * * * * ] rtrail [ 0 * * * * ] rtrail
coff m ρ n-ρ ctrail coff m ρ n-ρ ctrailwhere τ = rank D, B1 is full row rank, and E22 is upper triangular and nonsingular. The performed orthogonal or unitary transformations are accumulated in Q (i.e., Q <- Q*Q1), if withQ = true, and Z (i.e., Z <- Z*Z1), if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of M.
The matrix L is overwritten by Q1'*L unless L = missing and the matrix R is overwritten by R*Z1 unless R = missing.
MatrixPencils._preduce3! — Function_preduce3!(n::Int, m::Int, M::AbstractMatrix, N::AbstractMatrix,
Q::Union{AbstractMatrix,Nothing}, Z::Union{AbstractMatrix,Nothing}, tol,
L::Union{AbstractMatrix{T},Missing} = missing, R::Union{AbstractMatrix{T},Missing} = missing;
fast = true, roff = 0, coff = 0, rtrail = 0, ctrail = 0, withQ = true, withZ = true)Reduce the structured pencil
[ * * * * ] roff [ * * * * ] roff
M = [ 0 B A * ] n N = [ 0 0 E * ] n
[ 0 * * * ] rtrail [ 0 * * * ] rtrail
coff m n ctrail coff m n ctrailwith E upper triangular and nonsingular to the following form M1 - λN1 = Q1'*(M - λN)*Z1 with
[ * * * * * ] roff [ * * * * * ] roff
M1 = [ 0 B1 A11 A12 * ] ρ N1 = [ 0 0 E11 E12 * ] ρ
[ 0 0 A21 A22 * ] n-ρ [ 0 0 0 E22 * ] n-ρ
[ 0 * * * * ] rtrail [ 0 * * * * ] rtrail
coff m ρ n-ρ ctrail coff m ρ n-ρ ctrailwhere B1 has full row rank ρ and E11 and E22 are upper triangular and nonsingular. The performed orthogonal or unitary transformations are accumulated in Q (i.e., Q <- Q*Q1), if withQ = true, and Z (i.e., Z <- Z*Z1), if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of M.
The matrix L is overwritten by Q1'*L unless L = missing and the matrix R is overwritten by R*Z1 unless R = missing.
MatrixPencils._preduce2! — Function_preduce2!(n::Int, m::Int, p::Int, M::AbstractMatrix, N::AbstractMatrix,
Q::Union{AbstractMatrix,Nothing}, Z::Union{AbstractMatrix,Nothing}, tol,
L::Union{AbstractMatrix{T},Missing} = missing, R::Union{AbstractMatrix{T},Missing} = missing;
fast = true, roff = 0, coff = 0, rtrail = 0, ctrail = 0, withQ = true, withZ = true)Reduce the structured pencil
M = [ * * * * ] roff N = [ * * * * ] roff
[ * B A * ] n [ 0 0 E * ] n
[ * D C * ] p [ 0 0 0 * ] p
[ 0 0 0 * ] rtrail [ 0 0 0 * ] rtrail
coff m n ctrail coff m n ctrailwith E upper triangular and nonsingular to the following form M1 - λN1 = Q1'*(M - λN)*Z1 with
M1 = [ * * * * * ] roff N1 = [ * * * * * ] roff
[ * B1 A11 A12 * ] n-ρ [ 0 0 E11 E12 * ] n-ρ
[ * D1 C1 A22 * ] ρ [ 0 0 0 E22 * ] ρ
[ 0 0 0 C2 * ] p [ 0 0 0 0 * ] p
[ 0 0 0 0 * ] rtrail [ 0 0 0 0 * ] rtrail
coff m-τ n-ρ τ+ρ ctrail coff m-τ n-ρ τ+ρ ctrailwhere τ = rank D, C2 is full column rank and E11 and E22 are upper triangular and nonsingular. The performed orthogonal or unitary transformations are accumulated in Q (i.e., Q <- Q*Q1), if withQ = true, and Z (i.e., Z <- Z*Z1), if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of M.
The matrix L is overwritten by Q1'*L unless L = missing and the matrix R is overwritten by R*Z1 unless R = missing.
MatrixPencils._preduce4! — Function_preduce4!(n::Int, m::Int, p::Int, M::AbstractMatrix, N::AbstractMatrix,
Q::Union{AbstractMatrix,Nothing}, Z::Union{AbstractMatrix,Nothing}, tol,
L::Union{AbstractMatrix{T},Missing} = missing, R::Union{AbstractMatrix{T},Missing} = missing;
fast = true, roff = 0, coff = 0, rtrail = 0, ctrail = 0, withQ = true, withZ = true)Reduce the structured pencil
M = [ * * * * ] roff N = [ * * * * ] roff
[ 0 B A * ] n [ 0 0 E * ] n
[ 0 0 C * ] p [ 0 0 0 * ] p
[ 0 * * * ] rtrail [ 0 * * * ] rtrail
coff m n ctrail coff m n ctrailwith E upper triangular and nonsingular to the following form M1 - λN1 = Q1'*(M - λN)*Z1 with
M1 = [ * * * * * ] roff N1 = [ * * * * * ] roff
[ 0 B1 A11 A12 * ] n-ρ [ 0 0 E11 E12 * ] n-ρ
[ 0 B2 A21 A22 * ] ρ [ 0 0 0 E22 * ] ρ
[ 0 0 0 C1 * ] p [ 0 0 0 0 * ] p
[ 0 * * * * ] rtrail [ 0 * * * * ] rtrail
coff m n-ρ ρ ctrail coff m n-ρ ρ ctrailwhere C1 has full column rank and E11 and E22 are upper triangular and nonsingular. The performed orthogonal or unitary transformations are accumulated in Q (i.e., Q <- Q*Q1), if withQ = true, and Z (i.e., Z <- Z*Z1), if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of M.
The matrix L is overwritten by Q1'*L unless L = missing and the matrix R is overwritten by R*Z1 unless R = missing.
MatrixPencils._sreduceB! — Function_sreduceB!(A::AbstractMatrix{T},E::AbstractMatrix{T},B::AbstractMatrix{T},Q::Union{AbstractMatrix{T},Nothing}, tol::Real;
fast = true, withQ = true) -> ρReduce the n x m matrix B using an orthogonal or unitary similarity transformation Q1 to the row compressed form
BT = Q1'*B = [ B11 ] ρ
[ 0 ] n-ρ
mwhere B11 has full row rank ρ. Q1'*A, Q1'*E and BT are returned in A, E and B, respectively. The performed orthogonal or unitary transformations are accumulated in Q if withQ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of B.
MatrixPencils._sreduceBA! — Function_sreduceBA!(n::Int,m::Int,A::AbstractMatrix{T},B::AbstractMatrix{T},C::Union{AbstractMatrix{T},Missing},Q::Union{AbstractMatrix{T},Nothing}, tol::Real;
fast = true, init = true, roff = 0, coff = 0, withQ = true) -> ρReduce for init = true, the pair (A,B) using an orthogonal or unitary similarity transformation on the matrices A and B of the form H = Q1'*A*Q1, G = Q1'*B, to the form
G = [ B11 ] H = [ A11 A12 ] ρ
[ 0 ] B2 A22 ] n-ρ
m ρ n-ρwhere B11 has full row rank ρ. H, G and C*Q1 are returned in A, B and C, respectively. The performed orthogonal or unitary transformations are accumulated in Q if withQ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of B.
Reduce for init = false, the matrix A of the form
A = [ * * * ] roff
[ 0 B1 A1 ] n
coff m nusing an orthogonal or unitary similarity transformation on the submatrices A1 and B1 of the form H1 = Q1'A1Q1, G1 = Q1'*B1, to the form
[ * * * * ] roff
H = diag(I,Q1')*A*diag(I,Q1) = [ * B11 A11 A12 ] ρ
[ 0 0 B2 A22 ] n-ρ
coff m ρ n-ρwhere B11 has full row rank ρ. H and C*diag(I,Q1) are returned in A and C, respectively, and B is unchanged. The performed orthogonal or unitary transformations are accumulated in Q if withQ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of A.
MatrixPencils._sreduceBAE! — Function_sreduceBAE!(n::Int,m::Int,A::AbstractMatrix{T},E::AbstractMatrix{T},B::AbstractMatrix{T},C::Union{AbstractMatrix{T},Missing},
Q::Union{AbstractMatrix{T},Nothing}, Z::Union{AbstractMatrix{T},Nothing}, tol::Real;
fast = true, init = true, roff = 0, coff = 0, withQ = true, withZ = true)Reduce for init = true, the pair (A-λE,B), with E upper-triangular, using an orthogonal or unitary similarity transformations on the matrices A, E and B of the form At = Q1'*A*Z1, Et = Q1'*E*Z1, Bt = Q1'*B, to the form
Bt = [ B11 ] At = [ A11 A12 ] ρ Et = [ E11 E12 ] ρ
[ 0 ] B2 A22 ] n-ρ [ 0 E22 ] n-ρ
m ρ n-ρ ρ n-ρwhere B11 has full row rank ρ and Et is upper-triangular. Bt, At, Et and C*Z1 are returned in B, A, E and C, respectively. The performed orthogonal or unitary transformations are accumulated in Q as Q <- Q*Q1 if withQ = true and in Z as Z <- Z*Z1 if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of B.
Reduce for init = false, the matrices A and E of the form
A = [ * * * ] roff E = [ * * * ] roff
[ 0 B1 A1 ] n [ 0 0 E1 ] n
coff m n coff m nwith E1 upper triangular, using an orthogonal or unitary similarity transformations on the submatrices A1, E1 and B1 of the form At1 = Q1'*A1*Z1, Et1 = Q1'*E1*Z1, Bt1 = Q1'*B1, to the form
[ * * * * ] roff
At = diag(I,Q1')*A*diag(I,Z1) = [ 0 B11 A11 A12 ] ρ
[ 0 0 B2 A22 ] n-ρ
coff m ρ n-ρ
[ * * * * ] roff
Et = diag(I,Q1')*A*diag(I,Z1) = [ 0 0 E11 E12 ] ρ
[ 0 0 0 E22 ] n-ρ
coff m ρ n-ρwhere B11 has full row rank ρ, and E11 and E22 are upper triangular. At, Et and C*diag(I,Z1) are returned in A, E and C, respectively, and B is unchanged. The performed orthogonal or unitary transformations are accumulated in Q as Q <- Q*diag(I,Q1) if withQ = true and in Z as Z <- Z*diag(I,Z1) if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of A.
MatrixPencils._sreduceC! — Function_sreduceC!(A::AbstractMatrix{T},E::AbstractMatrix{T},C::AbstractMatrix{T},Z::Union{AbstractMatrix{T},Nothing}, tol::Real;
fast = true, withZ = true) -> ρReduce the p x n matrix C using an orthogonal or unitary similarity transformation Z1 to the column compressed form
CT = C*Z1 = [ 0 C11 ] p
n-ρ ρwhere C11 has full column rank ρ. A*Z1, E*Z1 and CT are returned in A, E and C, respectively. The performed orthogonal or unitary transformations are accumulated in Z if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of C.
MatrixPencils._sreduceAC! — Function_sreduceAC!(n::Int,p::Int,A::AbstractMatrix{T},C::AbstractMatrix{T},B::Union{AbstractMatrix{T},Missing},
Q::Union{AbstractMatrix{T},Nothing}, tol::Real;
fast = true, init = true, rtrail = 0, ctrail = 0, withQ = true) -> ρReduce for init = true, the pair (A,C) using an orthogonal or unitary similarity transformation on the matrices A and C of the form H = Q1'*A*Q1, L = C*Q1, to the form
H = [ A11 A12 ] n-ρ L = [ 0 C11 ] p
[ C2 A22 ] ρ n-ρ ρ
n-ρ ρwhere C11 has full column rank ρ. H, L and Q1'*B are returned in A, C and B, respectively. The performed orthogonal or unitary transformations are accumulated in Q if withQ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of C.
Reduce for init = false, the matrix A of the form
[ A1 * ] n
A = [ C1 * ] p
[ 0 * ] rtrail
n ctrailusing an orthogonal or unitary similarity transformation on the submatrices A1 and C1 of the form H1 = Q1'A1Q1, L1 = C1*Q1, to the form
[ A11 A12 * ] n-ρ
[ C2 A22 * ] ρ
H = diag(Q1',I)*A*diag(Q1,I) = [ 0 C11 * ] p
[ 0 0 * ] rtrail
n-ρ ρ ctrailwhere C11 has full column rank ρ. H and diag(Q1',I)*B are returned in A and B, respectively, and C is unchanged. The performed orthogonal or unitary transformations are accumulated in Q if withQ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of A.
MatrixPencils._sreduceAEC! — Function_sreduceAEC!(n::Int,p::Int,A::AbstractMatrix{T},E::AbstractMatrix{T},C::AbstractMatrix{T},B::Union{AbstractMatrix{T},Missing},
Q::Union{AbstractMatrix{T},Nothing}, Z::Union{AbstractMatrix{T},Nothing}, tol::Real;
fast = true, init = true, rtrail = 0, ctrail = 0, withQ = true, withZ = true) -> ρReduce for init = true, the pair (A-λE,C), with E upper-triangular, using an orthogonal or unitary similarity transformations on the matrices A, E and C of the form At = Q1'*A*Z1, Et = Q1'*E*Z1, Ct = C*Z1, to the form
Ct = [ 0 C11 ] p At = [ A11 A12 ] n-ρ Et = [ E11 E12 ] n-ρ
n-ρ ρ [ C2 A22 ] ρ [ 0 E22 ] ρ
n-ρ ρ n-ρ ρwhere C11 has full column rank ρ and Et is upper-triangular. Ct, At, Et and Q1'*B are returned in C, A, E and B, respectively. The performed orthogonal or unitary transformations are accumulated in Q as Q <- Q*Q1 if withQ = true and in Z as Z <- Z*Z1 if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of C.
Reduce for init = false, the matrices A and E of the form
[ A1 * ] n [ E1 * ] n
A = [ C1 * ] p E = [ 0 * ] p
[ 0 * ] rtrail [ 0 * ] rtrail
n ctrailwith E1 upper triangular, using an orthogonal or unitary similarity transformations on the submatrices A1, E1 and C1 of the form At1 = Q1'*A1*Z1, Et1 = Q1'*E1*Z1, Ct1 = C1*Z1, to the form
[ A11 A12 * ] n-ρ
[ C2 A22 * ] ρ
At = diag(Q1',I)*A*diag(Q1,I) = [ 0 C11 * ] p
[ 0 0 * ] rtrail
n-ρ ρ ctrail
[ E11 E12 * ] n-ρ
[ 0 E22 * ] ρ
Et = diag(Q1',I)*A*diag(Q1,I) = [ 0 0 * ] p
[ 0 0 * ] rtrail
n-ρ ρ ctrailwhere C11 has full column rank ρ, and E11 and E22 are upper triangular. At, Et and diag(I,Q1')*B are returned in A, E and B, respectively, and C is unchanged. The performed orthogonal or unitary transformations are accumulated in Q as Q <- Q*diag(I,Q1) if withQ = true and in Z as Z <- Z*diag(I,Z1) if withZ = true. The rank decisions use the absolute tolerance tol for the nonzero elements of A.