Lecture #13

EEE 574
Dr. Dan Tylavsky
Sparse Vector Methods
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Application: Consider faulted power systems.
Fault
+
-
V
pre-fault
+
-
-V
pre-fault
This system is electrically equivalent to:
By superposition:
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
+
-
V
pre-fault
+
-
-V
pre-fault
First system has 0.0 A. p.u. fault current, so
the total fault current may be calculated
using the second network.
To calculate fault current in
second system we first represent
the rest of the network as a
Thevenin equivalent.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Once we have the Thevenin equivalent at a bus,
we then calculate the fault current using the
following network:
+
-
V
O.C.
V
O.C.
I
S.C.
Z
thevenin
=
Z
thevenin
+
-
I
f
V
pre-fault
Assuming the network is linear, we find AN open
circuit voltage (assuming all internal sources are
deactivated) for A 1 p.u. current injection at the
node of interest.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
We can find the open circuit voltage by
solving the equation:
| |
(
(
(
(
(
(

= =
(
(
(
(
(
(

0
0 / 0 . 1
0
. .

o
C S k C O k
I
X
V
X
Y
Z
thevenin
I
f
=1.0 0
o
V
O.C.
-
+
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
( ) nodes adjacent k p V V Y I
k p k p k p
, ;
, ,
=
Once we find the Z
Thevenin
, we can then find
the short circuit current due to prefault
voltage V
PreFault
. Call that I
f
.
We then want the currents flowing in
branches near node, k, for instance.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
To get these voltages we need to solve problems
of the form:
| |
(
(
(
(
(
(

= =
(
(
(
(
(
(

0
0

Fault k k
p
I I
X
V
V
X
Y
X=dont care values
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Sometimes we wish to solve LUx=b when b is
sparse and the elements we want to know in x are
sparse.
When b and x are very sparse it is advantageous to
use sparse vector methods.
Defn: Elimination Tree - A graph specifying the
order in which rows of a matrix must be processed
(during factorization or F/B substitution) if all
precedence relationships are to be obeyed.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Theorem (Without Proof): All precedence relationships in LU
factorization and F/B substitution will be obeyed if the nodes
are ordered using the following algorithm:
The node k must immediately precede node j if the lowest
numbered below diagonal element in column k of L
occurs in row j.
(This is proved using the Fill-in Theorem.)
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
(
(
(
(
(
(
(
(
(

=
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(

7
6
5
4
3
2
1
7
6
5
4
3
2
1
77 76 73 72
66 65 62
55 54 51
44 41
33
22
11
b
b
b
b
b
b
b
x
x
x
x
x
x
x
l l l l
l l l
l l l
l l
l
l
l
1
4
5
6
7
2
3
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
L(U) Data structure requirements: The lowest-numbered,
non-zero off diagonal element in each column of L (row
of U) must be directly accessible without search (if
efficiency is to be maintained.)
* L(C), U(R), D, CO works.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Defn: Singleton - A vector with one non-zero
element.
Defn: Factoriztion Path (Factor Path, or Path) - An
ordered list of columns of L (rows of U) used in the
solution of Lx=b.
Defn: Singleton Path - Factor Path for a singleton.
The factor path for a group of singletons may be
found by appending to the front of each factor path
the unique elements of the factor path of subsequent
elements in the singleton list.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Example: Find the factor path for the singletons
b={b
1
, b
2
}, for the matrix shown below.
(
(
(
(
(
(
(
(
(

=
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(

7
6
5
4
3
2
1
7
6
5
4
3
2
1
77 76 73 72
66 65 62
55 54 51
44 41
33
22
11
b
b
b
b
b
b
b
x
x
x
x
x
x
x
l l l l
l l l
l l l
l l
l
l
l
Factor path ={ 1,4,5,6,7} 2,
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Teams: Draw the elimination tree for the following
L matrix from a factored A matrix and find the
factor path for the singletons b={b
4
, b
8
}.
(
(
(
(
(
(
(
(
(
(
(
(
(
(

10 10 9 10 8 10 7 10 6 10 4 10
99 98
88
77 76 75 71
66 65 63 61
55 53 52 51
44
33 32
22
11
l l l l l l
l l
l
l l l l
l l l l
l l l l
l
l l
l
l
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Elimination tree for IEEE 118 bus system.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
7
6
2
3
Example: For the following matrix, find the value for
x
2
, given that the only non-zero in the b vector is b
3
=2.
(
(
(
(
(
(
(
(
(

=
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(

2
1
5 1
3 1
2 1
2 1
1 5 . 0 1
2 2 1
1 5 2 1
1 3 5 . 0
1 2 2
1 2
1
1
1
7
6
5
4
3
2
1
x
x
x
x
x
x
x
Fast Forward Factor path ={3,7}
7
1
4
5
6
2
3
Fast Backward Factor path ={7,6,2}
w
w Ux b Lw Solve = = ; :
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
(
(
(
(
(
(
(
(
(

=
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(

2
1 5 2 1
1 3 5 . 0
1 2 2
1 2
1
1
1
7
3
w
w
4 , 0 2
2
7 7 3
3
= = +
=
w w w
w
Columns By
(
(
(
(
(
(
(
(
(

=
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(

4
2
1
5 1
3 1
2 1
2 1
1 5 . 0 1
2 2 1
7
6
2
x
x
x
6 ) 4 ( 20 * 5 . 0 5 .
20 , 0 5
4
2 7 6 2
6 7 6
7
= = = + +
= = +
=
x x x x
x x x
x
Rows By
b Lw Solve = : w Ux Solve = :
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Individually: For the following matrix, find the value
for x
8
, given that the only non-zeros in the b vector are
{b
4
, b
8
}={2,2}. (Process L by cols. U by rows.)
(
(
(
(
(
(
(
(
(
(
(
(
(
(

=
(
(
(
(
(
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(
(
(
(
(
(

2
2
1
2 1
3 1 1
7 . 10 1
6 . 10 6 . 7 1
9 . 6 18 1
5 1
3 12 1
3 . 7 6 . 5 1
6 21 4 . 8 1
1 2 3 7 . 10 6 . 10 5
1 1
1
1 6 . 7 9 . 6 6
1 18 3 21
1 12 3 . 7 4 . 8
1
1 6 . 5
1
1
10
9
8
7
6
5
4
3
2
1
x
x
x
x
x
x
x
x
x
x
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Example: Using a self-referential linked list construct
the factor path for the U matrix shown if the b vector
has non-zeros in position 2 and 5.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k):
ILP:
RIndxB(k): 2 5
End_B(k): 2
Switch(k): 0 0 0 0 0 0 0
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k):
ILP: 2
RIndxB(k): 2 5
End_B(k): 2 1.1
Switch(k): 0 1 0 0 0 0 0
Step 1.1: Enter position of first non-zero as Initial Link Pointer and in switch array. Step 1.2: Use ECP and Rindx to find factor path and enter in switch array.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k):
ILP: 2
RIndxB(k): 2 5
End_B(k): 2 1.2(a)
Switch(k): 0 1 0 0 0 0 0
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k): 6
ILP: 2
RIndxB(k): 2 5
End_B(k): 2 1.2(b)
Switch(k): 0 1 0 0 0 1 0
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k): 6 7
ILP: 2
RIndxB(k): 2 5
End_B(k): 2 1.2(c)
Switch(k): 0 1 0 0 0 1 1
Step 2.1: Compare next native b non-zero loc. w/ switch array and enter in link if new.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k): 6 7
ILP: 2
RIndxB(k): 2 5
End_B(k): 2 2.1
Switch(k): 0 1 0 0 0 1 1
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k): 6 2 7
ILP: 5
RIndxB(k): 2 5
End_B(k): 2 2.1(b)
Switch(k): 0 1 0 0 1 1 1
Step 2.2: Use ECP and Rindx to find factor path and merge into Link.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Step 2.2: Use ECP and Rindx to find factor path and merge into Link.
Example: Using a self-referential linked list construct
the factor path for the U matrix shown if the b vector
has non-zeros in position 2 and 5.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
L(k): 1 2 2 1 0.5 1 1 2 1 2 1 3 1 5 1
RIndx(k): 1 4 5 2 6 7 3 7 4 5 5 6 6 7 7
ECP(k): 0 3 6 8 10 12 14 15
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Link(k): 6 2 7
ILP: 5
RIndxB(k): 2 5
End_B(k): 2 2.2
Switch(k): 0 1 0 0 1 1 1
Result: Complete factor path is {5, 2, 6, 7}.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Example: Perform fast forward (FF) substitution
using the L/U matrix shown below if the b
3
=2, b
5
=1
(all other b
i
s are zero).
(
(
(
(
(
(
(
(
(

=
(
(
(
(
(
(
(
(
(

(
(
(
(
(
(
(
(
(

1
2
1 5 2 1
1 3 5 . 0
1 2 2
1 2
1
1
1
7
6
5
4
3
2
1
x
x
x
x
x
x
x
7
1
4
5
6
2
3
Factor Path = {5, 2, 6, 7}
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5
B(k): - - - - - - -
Step 0: Zero B locations according to factor path.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5
B(k): - 0 - - 0 0 0 0
Step 1: Overwrite B locations according to non-zeros.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5
B(k): - 2 - - 1 0 0 1
Step 2.1: Perform Forward substitution by columns for 1st element in path.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5 B(6)=B(6)-3*B(5)=0-3*1=-3
B(k): - 2 - - 1 0 0 1
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5 B(6)=B(6)-3*B(5)=0-3*1=-3
B(k): - 2 - - 1 -3 0 2.1
Step 2.2: Perform Forward substitution by columns for 2nd element in path.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5 B(6)=B(6)-.5*B(2)=-3-.5*2=-4
B(k): - 2 - - 1 -3 0 2.2(a)
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5 B(6)=B(6)-.5*B(2)=-3-.5*2=-4
B(k): - 2 - - 1 -4 0 2.2(b)
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5 B(7)=B(7)-1*B(2)=0-1*2=-2
B(k): - 2 - - 1 -4 0 2.2(c)
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5 B(7)=B(7)-1*B(2)=0-1*2=-2
B(k): - 2 - - 1 -4 -2 2.2(d)
Step 2.3: Perform Forward substitution by columns for 3rd element in path.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7 B(7)=B(7)-5*B(6)=-2-5*(-4)=18
ILP: 5
B(k): - 2 - - 1 -4 -2 2.3(a)
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7 B(7)=B(7)-5*B(6)=-2-5*(-4)=18
ILP: 5
B(k): - 2 - - 1 -4 18 2.3(b)
Step 2.4: Perform Forward substitution by columns for 4th element in path.
Pos: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
L(k): 2 2 0.5 1 2 2 3 5
RIndx(k): 4 5 6 7 7 5 6 7
ECP(k): 0 2 4 5 6 7 8
Pos: 0 1 2 3 4 5 6 7 8 9 10 11
Path(k): 6 2 7
ILP: 5
B(k): - 2 - - 1 -4 18 2.4
(If this matrix has elements on the diagonal, then operate else finished.)
Solution is {b
2
, b
5
, b
6
, b
7
}= {2, 1, -4, 18 }
Perform Fast Backward substitution using appropriately ordered factor path if
Ux=w is needed.
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
Results of using FF & FB:
Defn: (p:N N:k) as full (sparse) forward
substitution starting with row/column p and full
(sparse) backward substitution ending with
row/column k.
Scenario: b
k
is known, x
k
is desired.

) 1 : , : 1 (
3
N N in adds mult Total
FB and FF in adds mult Total
R

=
) : , : (
4
k N N k in adds mult Total
FB and FF in adds mult Total
R

=
Spare Vectors Methods
Copyright 1999 Daniel Tylavsky
System
Size
(Buses) Mean
R3
S.D. Mean
R4
S.D.
156 15% 6% 36% 25%
1598 5% 1% 12% 14%
2265 7% 2% 15% 14%
Defn: Neighborhood of length k about node m: The
set of all nodes which can be reached by starting at
node m and traversing at most k branches.
Results for 2265 Node System
Neighboo
rhood
Length
# of
Nodes
Path
Length
Mult.
Adds
0 1 39 728
1 3 39 733
2 6 42 748
3 10 45 765
Results show that getting
solutions for nodes in a
neighborhood of a node, k,
requires only slightly more
work than required for the
solution of only node k.
The End