# Combined Preorder and Postorder Traversal Algorithm for the Analysis of Singular Systems by Haar Wavelets

Authors: Beom-Soo Kim; Il-Joo Shim; Myo-Taeg Lim; Young-Joong Kim
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

An efficient computational method is presented for state space analysis of singular systems via Haar wavelets. Singular systems are those in which dynamics are governed by a combination of algebraic and differential equations. The corresponding differential-algebraic matrix equation is converted to a generalized Sylvester matrix equation by using Haar wavelet basis. First, an explicit expression for the inverse of the Haar matrix is presented. Then, using it, we propose a combined preorder and postorder traversal algorithm to solve the generalized Sylvester matrix equation. Finally, the efficiency of the proposed method is discussed by a numerical example.


---

## Body

## 1. Introduction

Wavelets
are  mathematical functions that cut up data into different frequency components
and then study each component with a resolution matched to its scale. Wavelets
are now being applied in many areas of science and engineering [1–4]. Much attention
has been focused on the use of wavelet transforms to investigate dynamic
systems. This is due to the powerful ability of wavelet transforms to decompose
time series in time-frequency domain and wavelet basis functions. Chen and
Hsiao [3, 4] derived a Haar operational matrix for integration and solved the
lumped and distributed parameter systems by constructing operational matrices
of various order. The main characteristic of this technique is that it converts
a differential equation into an algebraic one with the result that the solution
procedures are greatly reduced and simplified. This approach gives new insight
into the use of the Haar wavelet method.Singular
systems (also referred to as descriptor or semistate systems) arise more naturally
than do state-variable descriptions in the analysis of many sorts of systems.
Examples occur in electrical networks, neural networks, control systems,
chemical systems, economic systems, and so on (see [5, 6] and references
therein). These systems are governed by a mixture of differential and algebraic
equations. The complex nature of singular systems causes many difficulties in
the analytical and numerical treatment of such systems.Recently,
Haar wavelet technique was applied to state analysis and observer design of
singular systems [7]. This approach replaces the state function and the forcing
function by the truncated Haar series, respectively. Then the state
trajectories are obtained by solving a generalized Sylvester matrix equation. But
there exists a trade-off between the resolution of the wavelets and the
computation time. The accuracy of the solution can be achieved by increasing
the resolution level, but this requires more computation time and very large
memory.In
this paper, an efficient computational method is presented for state space
analysis of singular systems via Haar wavelets. First, an explicit expression
for the inverse of the Haar matrix is presented. This inverse matrix also has a
recursive structure. By using this matrix, we propose a combined preorder and
postorder traversal algorithm. Then, the full-order generalized Sylvester
matrix equation should be solved in terms of the solutions of simple linear
matrix equations. Finally, the efficiency of the proposed method is discussed
by a numerical example.


## 2. Kronecker Product

LetA=[aij] and B=[bij] be n×p and r×q matrices, respectively. The Kronecker product
of the matrices, denoted by A⊗B(∈Rnr×pq),
is defined as  (2.1)A⊗B=[a11Ba12B⋯a1pBa21Ba22Ba2pB⋮⋮an1Ban2B⋯anpB]. The vec operator transforms a matrix A of size n×p to a vector of size np×1 by stacking the columns of A.
Some
properties of the Kronecker product  are given below [8]: (2.2)(A+B)⊗C=A⊗C+B⊗C,(A⊗B)C=(AC⊗B),(A⊗B)(C⊗D)=(AC⊗BD),(A⊗B)T=AT⊗BT.


## 3. Haar Wavelets and Their Properties

Wavelets
constitute a family of functions constructed from dilation and translation of a
single function called the mother wavelet that generates orthogonal bases ofL2(R).
The simplest and most basic of the wavelet systems is the Haar wavelet which is
a group of square waves with magnitudes of ±1 in certain intervals and zeros elsewhere [9].
The scaling function φ0(t) and mother wavelet φ1(t) are defined by, respectively, (3.1)φ0(t)={1,t∈[0,1),0,t∉[0,1),φ1(t)={1,t∈[0,12),−1,t∈[12,1),0,t∉[0,1). Then,
all the other basis functions φk(t) are obtained by dilation and translation of
the mother wavelet as follows: (3.2)φk(t)=φ1(2nt−j)={1,t∈[ta,tb),−1,t∈[tb,tc),0,t∉[ta,tc), where k=2n+j,
integer n≥1 is a dilation parameter, integer 0≤j<2n is a shift parameter, and the intervals are
given by ta=m/2n, tb=(0.5+j)/2n,
and tc=(1+j)/2n.
Since the support of the Haar wavelet is [0,1),
any square integrable function y(t)∈L2[0,1) can be written as an infinite linear
combination of Haar functions (3.3)y(t)=∑k=0∞ckφk(t),t∈[0,1), where
the Haar coefficients are determined by (3.4)ck=〈y(t),φk(t)〉=2n∫01y(t)φk(t)dt, where 〈⋅,⋅〉 denotes the inner product. In practical
applications, Haar series are truncated to m terms, that is, (3.5)y(t)≅∑k=0m−1ckφk(t)=CmThm(t), where
Haar functions coefficient vector Cm and Haar functions vector hm are defined as Cm≜[c0c1⋯cm−1]T and hm(t)≜[φ0(t)φ1(t)⋯φm−1(t)]T.Integrals
of the Haar functions with respect to variablet form ramp and triangular waveforms standing
with uniform slope, respectively, at the positions of the corresponding
rectangular functions. The group of these integrals can be expressed as
follows: (3.6)∫01φ0(t)dt=t,t∈[ta,tb),∫01φk(t)dt={t−ta,t∈[ta,tb),−t+tc,t∈[tb,tc),0,t∉[ta,tc). Then,
the Haar matrix Hm is defined as (3.7)Hm(t)≜[hm(t0)hm(t1)⋯hm(tm−1)], where i/m≤ti≤(i+1)/m.Integration
of the Haar function vector can be written as(3.8)∫0thm(τ)dτ≅Pmhm(t), where Pm is the m-square operational matrix of integration which
satisfies the following recursive formula [3]: (3.9)Pm=[Pm/2−12mHm/212mHm/2−10m/2],P1=[12], where 0m/2 is an m/2-square zero matrix. The Haar matrix Hm also has the following recursive formula [3]: (3.10)Hm=[Hm/2⊗[11]Im/2⊗[1−1]],H1=[1]. Particularly,
it was proven that the following relationship holds [3]: (3.11)Hm−1=1mHmTDm, where Dm=diag(1122⋯2p−1⋯2p−1︸m/2) and p=log2m. This diagonal matrix Dm also can be represented in the recursive form (3.12)Dm=[Dm/20m/20m/2m2Im/2],D1=[1], where m=2k,k=1,2,…,J,
and J is called a resolution scale or level.We
present the following lemma which will be used to decompose the generalized Sylvester
matrix equation.Lemma 3.1.
LetHm be a Haar matrix defined in (3.10). Then, its
inverse matrix has the following recursive form: (3.13)Hm−1=[Hm/2−1⊗[0.50.5]Im/2⊗[0.5−0.5]].Proof.
We assume thatHm−1 has the following recursive structure: (3.14)Hm−1=[Hm/2−1⊗[ab]Im/2⊗[cd]], where a,b,c,d are constants to be determined. Now, we
multiply Hm and Hm−1: (3.15)HmHm−1=[(Hm/2⊗[11])(Hm/2−1⊗[ab])(Hm/2⊗[11]11)(Im/2⊗[cd]cd)(Im/2⊗[1−1]1−1)(Hm/2−1⊗[ab]ab)(Im/2⊗[1−1]1−1)(Im/2⊗[cd]cd)]. Then,
using the property of (A⊗B)(C⊗D)=AC⊗BD,
we obtain (3.16)HmHm−1=[Im/2⊗(a+b)Hm/2⊗(c+d)Hm/2−1⊗(a−b)Im/2⊗(c−d)]. Thus, a=b=0.5,c=0.5,d=−0.5 satisfy  HmHm−1=Hm−1Hm=I.


## 4. Singular Linear System

Consider a linear continuous-time singular system described by(4.1)Ex˙(t)=Ax(t)+Bu(t),x(0)=x0, where x(t)∈Rp denotes the vector of state variables, u(t)∈Rq denotes the vector of manipulated inputs, E, A are p×p matrices, E is generally singular, and B is a p×q matrix. Without loss of generality, we assume
that rank(A)=p and (4.1) is regular, that is, det(λE−A)≠0.
Regularity means that the solution x(t) is uniquely determined by the given initial
value x0 and input u(t).If
the input function vectoru(t) is square integrable in the interval [0,1),
then it can be represented in a Haar function basis hm(t) as (4.2)u(t)=Ghm(t), where G∈Rq×m is a Haar coefficient matrix and can be obtained by the method described in Section 3.
Likewise, x˙(t) is expanded in Haar function basis (4.3)x˙(t)=Vhm(t), where V∈Rp×m is the unknown matrix to be determined. From
the definition of the Haar function, the initial state can be represented as
follows: (4.4)x0=[x00⋯0]hm(t). Integrating
(4.3) from 0 to t,
we have (4.5)x(t)=VPmhm(t)+x0. Integrating
(4.1) and using (3.8) and (4.4), after canceling hm(t),
we obtain (4.6)EV−AVPm=Q, where
we define Q≜[Ax00⋯0]+BG.
Thus, the differential matrix equation (4.1) has been transformed to a
generalized Sylvester matrix equation that must be solved for V.
Equation (4.6) can be solved by using Kronecker product as in [6] (4.7)(Im⊗E+PmT⊗A)vec(V)=vec(Q), where Im is a unit matrix. Equation (4.7) can be solved
by LU factorization. However, the coefficient matrix Im⊗E+PmT⊗A has dimension pm×pm,
making this approach impractical except for small systems. There are other
methods for solving the Sylvester matrix equation (4.6), for example, the
Bartels-Stewart algorithm, Krylov subspace method, and matrix sign function
method (see [10] and references therein). In [3, 11], recursive algorithms were
derived to solve the equations of type V−AVPm=Q for linear systems. It should be noted that the
algorithm in [3] is  not applicable to a generalized Sylvester matrix equation
(4.6), since E is a singular matrix.


### 4.1. Decomposition and Recursive Binary Tree

Under
the assumption thatA is a nonsingular matrix, (4.6) can be written
as the following Sylvester equation: (4.8)A−1EV−VPs=A−1Q. To
decompose (4.8), we split V and A−1Q by columns: (4.9)AE[V1(1)V1(2)]−[V1(1)V1(2)][Pm/2−12mHm/212mHm/2−10m/2]=[QaQb], where AE≜A−1E, A−1Q=[QaQb], V=[V1(1)V1(2)] with Qa,Qb,V1(1),V1(2)∈Rp×m/2.
Here Vk(r) denotes the matrix that is decomposed at level k with r={2k,2k−1}.
Then, we obtain the following reduced-order matrix equations: (4.10)AEV1(1)−V1(1)Pm/2−12mV1(2)Hm/2−1=Qa.(4.11)AEV1(2)+12mV1(1)Hm/2=Qb. Since E is a singular matrix, AE is also singular. Thus, we postmultiply by Hm/2−1 both sides of (4.11) to express V1(1) in terms of V1(2)(4.12)V1(1)=−2mAEV1(2)Hm/2−1+2mQbHm/2−1. Substituting
(4.12) into (4.10) yields (4.13)−2mAE2V1(2)Hm/2−1+2mAEQbHm/2−1+2mAEV1(2)Hm/2−1Pm/2−2mQbHm/2−1Pm/2−12mV1(2)Hm/2−1=Qa. Therefore,
the original problem is decomposed into a reduced-order generalized Sylvester
matrix equation (4.13) and a matrix algebraic equation (4.12). Again
postmultiplying by Hm/2 both sides of (4.13), we have(4.14)(−2mAE2−12mI)V1(2)+2mAEV1(2)Hm/2−1Pm/2Hm/2=QaHm/2−2mAEQb+2mQbHm/2−1Pm/2Hm/2. In
(4.14), we define (4.15)Cm/2≜Hm/2−1Pm/2Hm/2. Then,
the matrix Cm/2 is an upper triangular matrix and has the
following recursive form: (4.16)Cm/2=[12Cm/42m1m/40m/412Cm/4],C1=[12], where 1m/4 denotes m/4-square matrix with all elements being 1 (see Appendix ).Substituting
(4.16) into (4.14) and splitting V1(2) and the right-hand side of (4.14) by columns
yields (4.17)Ah[V2(3)V2(4)]+2mAE[V2(3)V2(4)][12Cm/42m1m/40m/412Cm/4]=[T2(3)T2(4)], where (4.18)Ah≜(−2mAE2−12mI),QaHm/2−2mAEQb+2mQbCm/2≜T1(2)=[T2(3)T2(4)],V1(2)=[V2(3)V2(4)]. Thus,
(4.17) is decomposed into two matrix equations with dependent and independent
subsystems. (4.19)AhV2(3)+mAEV2(3)Cm/4=T2(3).(4.20)AhV2(4)+mAEV2(4)Cm/4=T2(4)−4AEV2(3)1m/4. In
(4.19) and (4.20), we first solve for V2(3) and then after updating the right-hand side of
(4.20) with respect to V2(3),
solve for V2(4).
Since (4.19) and (4.20) have the same form as (4.17) and Cm/4 is still an upper triangular matrix, they can
be decomposed into two subsystems in which the dimension has been reduced by
half, respectively. Therefore, we recursively decompose each equation into two
equations until no further decomposition is possible in which all VJ(r),TJ(r)(r=2J−1+1,…,2J) are column vectors. This procedure
constructs the binary tree as shown in Figure 1.Figure 1
Binary tree for resolution scaleJ=4.A
binary tree is a rooted tree in which each node has at most two children,
designated as a left child and a right child. A full binary tree is a binary
tree in which each node has exactly two children or none. A perfect (or
complete) binary tree is a full binary tree in which all leaves have the same
depth [12]. In Figure 1, the binary tree in the dotted box is a perfect binary
tree of depth J-1.
An external node (or leaf node) is a node with no children. For instance, the
nodes labeled 1, 9, 10, 11, 12, 13, 14, 15, and 16 in Figure 1 are external
nodes.Matrix
equations corresponding to all external nodes of the perfect binary tree are
classified into two types of equations described as follows:(4.21)AhVJ(r)+4AEVJ(r)C1=TJ(r),r=2J−1+1,2J−1+3,…,2J−1(ris  odd),AhVJ(r)+4AEVJ(r)C1=TJ(r)−4AEVJ(r−1)11,r=2J−1+2,2J−1+4,…,2J(ris even). Note
that in equation (4.21), C1=1/2, 11=1.
Thus, they become simple linear matrix equations as follows: (4.22)(Ah+2AE)VJ(r)=TJ(r),ifrisodd,(Ah+2AE)VJ(r)=TJ(r)−4AEVJ(r−1),ifriseven.


### 4.2. Combined Preorder and Postorder Traversal Algorithm

Visiting
all the nodes in a tree in some particular order is known as a tree traversal. A preorder traversal visits the root of a subtree, then the
left and right subtrees recursively. A postorder traversal visits the left and
right subtrees recursively, then the root node of the subtree [12]. For
example, the preorder and postorder traversals of the binary tree shown in Figure 1 are as follows:During
the decomposition of (4.14), the right-hand side of the right child is split
after updating it recursively as follows: (4.23)Tk(r)−4AEVk(r−1)1m/2k=[Tk+1(2r−1)Tk+1(2r)]. This
splitting and updating sequence is a preorder traversal of the perfect binary
tree from root node ②. The unknown matrix V1(2) is obtained by merging all column vectors VJ(r)(r=2J−1+1,…,2J). This sequence is a postorder traversal of
the perfect binary tree from root node ②. To update (4.23), we need Vk(r−1) which is obtained from the left child. Hence,
to solve (4.22), it is necessary to update, split, and solve by using
the following combined preorder and postorder traversal method.The
pseudocode of the proposed algorithm is as in Algorithm1.Algorithm 1
Step 1. InitializeAh,AE,T.Step 2. ObtainV1(2)Input:ResolutionscaleJWaveSolver(J){for(r=2J-1+1;r<2J;r=r+2){Solve  forVJ(r)the  system(Ah+2AE)VJ(r)=TJ(r)UpdateTJ(r+1)accroding  toTJ(r+1)=TJ(r+1)−4AEVJ(r)Solve  forVJ(r+1)the  system(Ah+2AE)VJ(r+1)=TJ(r+1)WaveTree(1,J,r+1)}}Input:rnoisanumberofrecursivecall.ResolutionscaleJrisanodenumber.WaveTree(rno,J,r){if(J-rno≤0)returnMerge:VJ-rno(r/2)=[VJ-rno+1(r−1)VJ-rno+1(r)]if(r2is  even)WaveTree(rno+1,J,r2);elseUpdate  and  Split:[TJ-rno+1(r-1)TJ-rno+1(r)]=TJ−rno(r/2+1)−4AEVJ-rno(r/2)1m/2J-rno}Step 3. SolveV1(1)from(4.12).For
example, at resolution scaleJ=4,
the proposed combined preorder and postorder traversal method is  illustrated in
Figure 2.Figure 2
The combined preorder and
postorder traversal for resolution scaleJ=4.In
Figure2, nodes 2, 3, 5, and 9 of preorder traversal are done at Step 1 and the
remaining nodes are processed at Step 2. The computational efficiency of the
proposed method is discussed in the next section.


## 4.1. Decomposition and Recursive Binary Tree

Under
the assumption thatA is a nonsingular matrix, (4.6) can be written
as the following Sylvester equation: (4.8)A−1EV−VPs=A−1Q. To
decompose (4.8), we split V and A−1Q by columns: (4.9)AE[V1(1)V1(2)]−[V1(1)V1(2)][Pm/2−12mHm/212mHm/2−10m/2]=[QaQb], where AE≜A−1E, A−1Q=[QaQb], V=[V1(1)V1(2)] with Qa,Qb,V1(1),V1(2)∈Rp×m/2.
Here Vk(r) denotes the matrix that is decomposed at level k with r={2k,2k−1}.
Then, we obtain the following reduced-order matrix equations: (4.10)AEV1(1)−V1(1)Pm/2−12mV1(2)Hm/2−1=Qa.(4.11)AEV1(2)+12mV1(1)Hm/2=Qb. Since E is a singular matrix, AE is also singular. Thus, we postmultiply by Hm/2−1 both sides of (4.11) to express V1(1) in terms of V1(2)(4.12)V1(1)=−2mAEV1(2)Hm/2−1+2mQbHm/2−1. Substituting
(4.12) into (4.10) yields (4.13)−2mAE2V1(2)Hm/2−1+2mAEQbHm/2−1+2mAEV1(2)Hm/2−1Pm/2−2mQbHm/2−1Pm/2−12mV1(2)Hm/2−1=Qa. Therefore,
the original problem is decomposed into a reduced-order generalized Sylvester
matrix equation (4.13) and a matrix algebraic equation (4.12). Again
postmultiplying by Hm/2 both sides of (4.13), we have(4.14)(−2mAE2−12mI)V1(2)+2mAEV1(2)Hm/2−1Pm/2Hm/2=QaHm/2−2mAEQb+2mQbHm/2−1Pm/2Hm/2. In
(4.14), we define (4.15)Cm/2≜Hm/2−1Pm/2Hm/2. Then,
the matrix Cm/2 is an upper triangular matrix and has the
following recursive form: (4.16)Cm/2=[12Cm/42m1m/40m/412Cm/4],C1=[12], where 1m/4 denotes m/4-square matrix with all elements being 1 (see Appendix ).Substituting
(4.16) into (4.14) and splitting V1(2) and the right-hand side of (4.14) by columns
yields (4.17)Ah[V2(3)V2(4)]+2mAE[V2(3)V2(4)][12Cm/42m1m/40m/412Cm/4]=[T2(3)T2(4)], where (4.18)Ah≜(−2mAE2−12mI),QaHm/2−2mAEQb+2mQbCm/2≜T1(2)=[T2(3)T2(4)],V1(2)=[V2(3)V2(4)]. Thus,
(4.17) is decomposed into two matrix equations with dependent and independent
subsystems. (4.19)AhV2(3)+mAEV2(3)Cm/4=T2(3).(4.20)AhV2(4)+mAEV2(4)Cm/4=T2(4)−4AEV2(3)1m/4. In
(4.19) and (4.20), we first solve for V2(3) and then after updating the right-hand side of
(4.20) with respect to V2(3),
solve for V2(4).
Since (4.19) and (4.20) have the same form as (4.17) and Cm/4 is still an upper triangular matrix, they can
be decomposed into two subsystems in which the dimension has been reduced by
half, respectively. Therefore, we recursively decompose each equation into two
equations until no further decomposition is possible in which all VJ(r),TJ(r)(r=2J−1+1,…,2J) are column vectors. This procedure
constructs the binary tree as shown in Figure 1.Figure 1
Binary tree for resolution scaleJ=4.A
binary tree is a rooted tree in which each node has at most two children,
designated as a left child and a right child. A full binary tree is a binary
tree in which each node has exactly two children or none. A perfect (or
complete) binary tree is a full binary tree in which all leaves have the same
depth [12]. In Figure 1, the binary tree in the dotted box is a perfect binary
tree of depth J-1.
An external node (or leaf node) is a node with no children. For instance, the
nodes labeled 1, 9, 10, 11, 12, 13, 14, 15, and 16 in Figure 1 are external
nodes.Matrix
equations corresponding to all external nodes of the perfect binary tree are
classified into two types of equations described as follows:(4.21)AhVJ(r)+4AEVJ(r)C1=TJ(r),r=2J−1+1,2J−1+3,…,2J−1(ris  odd),AhVJ(r)+4AEVJ(r)C1=TJ(r)−4AEVJ(r−1)11,r=2J−1+2,2J−1+4,…,2J(ris even). Note
that in equation (4.21), C1=1/2, 11=1.
Thus, they become simple linear matrix equations as follows: (4.22)(Ah+2AE)VJ(r)=TJ(r),ifrisodd,(Ah+2AE)VJ(r)=TJ(r)−4AEVJ(r−1),ifriseven.


## 4.2. Combined Preorder and Postorder Traversal Algorithm

Visiting
all the nodes in a tree in some particular order is known as a tree traversal. A preorder traversal visits the root of a subtree, then the
left and right subtrees recursively. A postorder traversal visits the left and
right subtrees recursively, then the root node of the subtree [12]. For
example, the preorder and postorder traversals of the binary tree shown in Figure 1 are as follows:During
the decomposition of (4.14), the right-hand side of the right child is split
after updating it recursively as follows: (4.23)Tk(r)−4AEVk(r−1)1m/2k=[Tk+1(2r−1)Tk+1(2r)]. This
splitting and updating sequence is a preorder traversal of the perfect binary
tree from root node ②. The unknown matrix V1(2) is obtained by merging all column vectors VJ(r)(r=2J−1+1,…,2J). This sequence is a postorder traversal of
the perfect binary tree from root node ②. To update (4.23), we need Vk(r−1) which is obtained from the left child. Hence,
to solve (4.22), it is necessary to update, split, and solve by using
the following combined preorder and postorder traversal method.The
pseudocode of the proposed algorithm is as in Algorithm1.Algorithm 1
Step 1. InitializeAh,AE,T.Step 2. ObtainV1(2)Input:ResolutionscaleJWaveSolver(J){for(r=2J-1+1;r<2J;r=r+2){Solve  forVJ(r)the  system(Ah+2AE)VJ(r)=TJ(r)UpdateTJ(r+1)accroding  toTJ(r+1)=TJ(r+1)−4AEVJ(r)Solve  forVJ(r+1)the  system(Ah+2AE)VJ(r+1)=TJ(r+1)WaveTree(1,J,r+1)}}Input:rnoisanumberofrecursivecall.ResolutionscaleJrisanodenumber.WaveTree(rno,J,r){if(J-rno≤0)returnMerge:VJ-rno(r/2)=[VJ-rno+1(r−1)VJ-rno+1(r)]if(r2is  even)WaveTree(rno+1,J,r2);elseUpdate  and  Split:[TJ-rno+1(r-1)TJ-rno+1(r)]=TJ−rno(r/2+1)−4AEVJ-rno(r/2)1m/2J-rno}Step 3. SolveV1(1)from(4.12).For
example, at resolution scaleJ=4,
the proposed combined preorder and postorder traversal method is  illustrated in
Figure 2.Figure 2
The combined preorder and
postorder traversal for resolution scaleJ=4.In
Figure2, nodes 2, 3, 5, and 9 of preorder traversal are done at Step 1 and the
remaining nodes are processed at Step 2. The computational efficiency of the
proposed method is discussed in the next section.


## 5. An Illustrated Example

In
this section, an example is presented to illustrate the proposed algorithm. We
consider a singular linear system of (4.1) with (5.1)E=[1000010000000001],A=[−3301.000101.00621.4−28.2700−327.112.721],B=[0052.65−23.69], and X0=[00.51.00]T.
And we assume that u(t) is a unit step function. In the cases of J=4 and 8,
the simulation results are depicted in Figures 3 and 4, respectively.Figure 3
Case for resolution scaleJ=4.Figure 4
Case for resolution scaleJ=8.From
these figures, it is clear that the solution accuracy is improved when the
resolution scale is increased. However, it requires more computational time.In
(4.7), the LU factorization of Im⊗E+PmT⊗A involves O(m3p3) flops. The cost of the proposed algorithm is
the sum of the cost of WinSolver, O((m/2)p3+(m/2)p2),
and the cost of WinTree, O(∑k=1J−2(2J−1p2+(2J+2k−2−2J−2)p)) (see Appendix ). Since m=2J,
the costs of WinSolver and O(m3p3) can be rewritten as O(2J−1p3+2J−1p2) and O(23Jp3),
respectively. Thus, the total  cost of the proposed algorithm is (5.2)O(2J−1p3+2J−1p2+∑k=1J−2(2J−1p2+(2J+2k−2−2J−2)p))flops. Table 1 and Figure 5 show that the computational cost of the proposed algorithm is
significantly less than the Kronecker product method, and that the flop counts
are increasing rapidly with resolution scale. As the resolution scale grows,
the flop counts of WinTree is increasing more rapidly than that of WinSolver since the sizes of matrices 1m,Tm, and Vm increase exponentially.Table 1
Flop counts for
various sizes of the matrixA and resolution scales.
JA∈R4×4A∈R20×20KroneckerProposed algorithmKroneckerProposed algorithmmethodWinSolverWinTreeTotalmethodWinSolverWinTreeTotal240961600160512000168000168005209715212803360464026214400013440032160166560106.871×10104096089534464895754248.589×10124300800448983040453283840124.398×10121638405.726×1095.727×1095.497×1014172032002.864×10102.867×1010152.251×101513107202.932×10122.932×10122.814×10171376256001.466×10131.466×1013181.152×1018104857601.501×10151.501×10151.441×102011010048007.506×10157.506×1015207.378×1019838860804.194×10164.194×10169.223×10214.404×1094.803×10174.803×1017Figure 5
Log plot of flop
counts for the Kronecker product method and the proposed method.


## 6. Conclusions

An
efficient computational method was presented for state space analysis of
singular systems via Haar wavelets. The problem was formulated as a generalized
Sylvester matrix equation. We presented an explicit expression for the inverse
of the Haar matrix and a combined preorder and postorder traversal algorithm to
solve the problem more effectively. The full-order generalized Sylvester matrix
equation was solved in terms of the solutions of simple linear matrix equations
by the proposed algorithm. The efficiency of the proposed method was demonstrated
by a numerical example.



---

*Source: 323080-2008-10-26.xml*