Information Technology Reference
In-Depth Information
and if
I
is not an empty set, we do the above reduction step.
Therefore it is easy to check that the new updated basis returns to the situation
satisfying Condition 1, 2 and 3 when
I
becomes an empty set. Set
r
Set
I
←
I/
{
s
}
r
+1 and
we proceed with the algorithm from there. We give the algorithm as follows.
←
Algorithm 4.1
Input: the first
N
terms of a matrix sequence
T
=(
T
1
,T
2
,...
).
Output: an
N
th minimal partial realization of
T
.
1. Initialize
ω
1
←−ε
1
, ···,ω
p
←−ε
p
,ω
p
+1
← α
N,
1
,
···
,
ω
n
← α
N,m
,
r ←
0.
2.
While
there is an element
ω
s
,
p
+1
≤
s
≤
n
,with
θ
(
ω
s
)=
0
m
do
Set
I
=
{
p
+1
≤
s
≤
n
:
θ
(
ω
s
)=
0
m
and
N
s
=
v
(
η
(
ω
s
))
−
v
(
ω
s
) is minimal
}
.
While
I
do
Choose an integer
s
=
∅
∈
I
and so there exists a vector (
a
1
,...,a
p
) such that
θ
(
ω
s
)=
j
=1
a
j
θ
(
ω
j
) and find an integer
h
such that
v
(
ω
h
)=max
{
v
(
ω
j
):
1
≤
j
≤
p, a
j
=0
}
.
If
v
(
ω
s
)
≥
v
(
ω
h
)
then
ω
s
−
j
=1
a
j
z
−v
(
ω
j
)+
v
(
ω
s
)
ω
j
Set
ξ
←
else
set
ξ
z
−v
(
ω
s
)+
v
(
ω
h
)
ω
s
−
j
=1
a
j
z
−v
(
ω
j
)+
v
(
ω
h
)
ω
j
,
ω
h
←
←
ω
s
end-If
set
ω
s
←
ξ
and
I
←
I/
{
s
}
.
end-While
r
+1.
end-While
3. Set
M
N
(
z
)
r
←
(
η
(
ω
p
+
i
))
1
≤i≤m
, output pol(
T
(
z
)
M
N
(
z
))
M
−
1
N
←
(
z
), and termi-
nate the algorithm.
The above algorithm requires much memory and so it is not ecient in practice
when
N
is very large. Similar to the method in [20], we deduce an ecient
iterative algorithm from Algorithm 4.1. Here we only simply describe the idea.
Note that for every basis element
ω
i
,1
n
, we only use its three parameters,
that is,
v
(
ω
i
)
,θ
(
ω
i
)and
η
(
ω
i
) and so we suce to keep track of those values,
which can be represented from the information of the given matrix sequence
T
,
that is,
v
(
ω
i
)=
≤
i
≤
N
i
+
v
(
η
(
ω
i
)),
θ
(
ω
i
)=(
δ
N
i
(
η
(
ω
i
)
,T
)
,
0
m
)
t
.Thuswecanderive
the following algorithm from algorithm 4.1.
−
Algorithm 4.2
Input: the first
N
terms of a matrix sequence
T
=(
T
1
,T
2
,...
).
Output: an
N
th minimal partial realization of
T
.
1. For
i
=1
,...,p
,set
c
i
(
z
)
IF
p
,and
0
m
,
δ
i
←
←
(0
,...,
0
i−
1
,
−
1
,
0
,...,
0)
∈
IF
m
.
v
i
←
0. For
i
=1
,...,m
,set
M
0
,i
(
z
)=(0
,...,
0
i−
1
,
1
,
0
,...,
0)
∈
k
←
0.
