Information Technology Reference
In-Depth Information
So far we can solve the minimal partial realization problem by Theorem 1, The-
orem 2 and Theorem 3. We give our algorithm below, in which we give the
initialization in step 1, transform the initial basis into a reduced one in step 2,
and into a normal one in step 3. Finally we output the result in step 4.
Algorithm 2.1
Input: the first
N
terms of a matrix sequence
T
=(
T
1
,T
2
,...
).
Output: an
N
th minimal realization of
T
.
1. Initialize
ω
1
←−
ε
1
,
···
,ω
p
←−
ε
p
,ω
p
+1
←
α
N,
1
,
···
,
ω
n
←
α
N, m
.
2.
While
θ
(
ω
1
)
,
,θ
(
ω
n
) are linearly dependent over IF
do
(Reduction step)There is a vector (
a
1
,
···
,a
n
) such that
i
=1
a
i
θ
(
ω
i
)=
0
n
and find an integer
h
such that
v
(
ω
h
)=max
···
{
v
(
ω
i
): 1
≤
i
≤
m, a
i
=0
}
.
←
i
=1
a
i
z
−v
(
ω
i
)+
v
(
ω
h
)
ω
i
and
ω
h
←
Set
ξ
ξ
.
end-While
3.
For
j
=1
,...,m
do
Find an integer
k
such that
v
(
ω
k
)=min
{
v
(
ω
i
):1
≤
i
≤
n
and the (
p
+
j
)th
component of
θ
(
ω
i
) is nonzero
}
and set
c
k
←
the (
p
+
j
)-th component of
θ
(
ω
k
).
For
i
=1
,...,n
do
If
i
=
k
and the (
p
+
j
)-th component
c
of
θ
(
ω
i
) is not zero
then
set
ω
i
←
c
k
z
−v
(
ω
k
)+
v
(
ω
i
)
ω
k
and
ω
k
←
c
1
ω
i
−
c
k
ω
k
.
end-If
end-For
end-For
Arrange the
ω
i
in such a way such that
θ
(
ω
i
)=
0
m
,
i
=1
,...,p
,
v
(
ω
1
)
≤
...
≤
v
(
ω
p
)and
θ
(
ω
p
+
i
)
∈
[
β
i
]for1
≤
i
≤
m
.
(
η
(
ω
p
+
i
))
1
≤i≤m
, output pol(
T
(
z
)
M
N
(
z
))
M
−
1
N
4. Set
M
N
(
z
)
←
(
z
)andtermi-
nate the algorithm.
Remark 1.
When
m
= 1 the above algorithm becomes the synthesis algorithm
for vector sequences as in [20]. Similar to [20] we also show that the algorithm will
terminate in the finite steps. We introduce a function
Ψ
(
ω
1
,
···
,ω
n
)=
−
m
(
N
+
−
i
=1
v
(
ω
i
). Whenever a reduction step takes place, the value of
Ψ
(
ω
1
,
1)
···
,
ω
m
+1
) strictly increases by the above discussions and when
Ψ
(
ω
1
,
,ω
m
+1
)=0
the corresponding basis becomes reduced [17]. Thus the number of reduction
steps is at most
m
(
N
+1).
···
3
Parametrization of All Minimal Partial Realizations
and the Uniqueness Issue
Given a normal basis
ω
1
,...,ω
n
of the lattice
Λ
, put
π
i
=
v
(
ω
i
). Then the set
{
is completely determined by the lattice
Λ
and does not depend on
the particular normal basis
ω
1
,...,ω
n
[17]. It is easy to see that the lattice
Λ
is
completely determined by
T
and
N
, and so the set can be as the invariance of
the first
N
terms of the matrix sequence
T
.Since
ω
p
+
i
∈
π
1
,...,π
n
}
S
i
(
Λ
), it is easy to get
