a = -50 - 2x1 + 8x2 + 10x4 b = -100 + 5x1 + 2x2 c = -25 + 3x1 - 5x2 + 10x3 - 2x4 z = 0 - x1 - x2 - x3 - x4Here the initial basic solution is not feasible, so we construct the auxilary problem:
a = -50 - 2x1 + 8x2 + 10x4 + x0 b = -100 + 5x1 + 2x2 + x0 c = -25 + 3x1 - 5x2 + 10x3 - 2x4 + x0 z = -x0Rewriting x0 in terms of b, we get
x0 = 100 + b - 5x1 - 2x2 a = 50 + b - 7x1 + 6x2 + 10x4 c = 75 + b -2x1 - 7x2 + 10x3 - 2x4 z = -100 - b + 5x1 + 2x2Rewriting x1 in terms of a, we get
x1 = [50 - a + b + 6x2 + 10x4]/7 x0 = [450 + 5a + 2b - 44x2 - 50x4]/7 c = [425 + 2a + 5b - 61x2 + 10x3 - 34x4]/7 z = [-450 - 5a - 2b + 44x2 + 50x4]/7Rewriting x2 in terms of c, we get
x2 = [425 + 2a + 5b - 7c + 70x3 - 34x4]/61 x1 = [800 - 7a + 13b - 6c + 60x3 + 58x4]/61 x0 = [1250 + 31a - 14b + 44c - 440x3 - 222x4]/61 z = [-1250 - 31a + 14b - 44c + 440x3 + 222x4]/61Rewriting x3 in terms of x0, we get
x3 = [1250 + 31a - 14b + 44c - 61x0 - 222x4]/440 x2 = [4500 + 50a + 20b - 70x0 - 500x4]/440 x1 = [7000 - 20a + 80b - 60x0 + 200x4]/440 z = -x0This gives us a solution to the auxiliary problem in which 0 is the maximal value for -x0. Plugging the values for x1, x2, and x3 into the equation for z in the original (maximization) problem, we get
x3 = [1250 + 31a - 14b + 44c - 222x4]/440 x2 = [4500 + 50a + 20b - 500x4]/440 x1 = [7000 - 20a + 80b + 200x4]/440 z = [-12750 - 61a - 86b - 44c + 82x4]/440Rewriting x4 in terms of x3, we get
x4 = [1250 + 31a - 14b + 44c - 440x3]/222 x2 = [850 + other stuff]/222 x1 = [4100/ + other stuff]/222 z = [-6200 - 250a - 46b - 14c - 82x3]/222Since all coefficients in the equation for z are negative, we are done, with a solution (recalling that z needs to be negated to convert back to a minimization problem) of
x1 = 4100/222 x2 = 850/222 x4 = 1250/222 z = 6200/222This solution can be checked as follows: Since there are fewer constraints that variables, we might expect that all of the constraints can be met exactly. The second constraint has few nonzero terms and the 5x1 term dominates both this constraint and all of the other x1 terms, so we might expect it to have value a little less than 20 -- say 20 - 2p. Then using the second, first, and third constraints in that order, we get
x2 = 5p x4 = 9 - 4.4p x3 = -1.7 + 2.22p z = 27.3 + 0.84pThis is a minimization problem, so to minimize z we need to minimize p. If p is 0 or less, then x2 is negative. To make x2 minimially nonnegative (and also satisfy the other constraints), we set p to 1.7/2.22 = 170/222. Then x3 = 0, x2 = 5p = 850/222, and x1 and x4 can also be seen to take on the values given above for them.
z = -x1 - x2 - x3
x4 = -10000 + 2x1 + 7.5x2 + 3x3
x5 = -30000 + 20x1 + 5x2 + 10x3
initial solution isn't feasible, so let
z = -x0
x4 = -10000 + 2x1 + 7.5x2 + 3x3 + x0
x5 = -30000 + 20x1 + 5x2 + 10x3 + x0
swap x0 with x5; the equation for x0 is given below
z = -30000 + 20x1 + 5x2 + 10x3 - x5
x4 = 20000 - 18x1 + 2.5x2 + -7x3 + x5
x0 = 30000 - 20x1 - 5x2 - 10x3 + x5
swap x1 with x4; the equation for x1 is given below
z = -70000/9 + 70x2/9 + 20x3/9 - 10x4/9 + x5/9
x0 = 70000/9 - 70x2/9 - 20x3/9 + 10x4/9 - x5/9
x1 = 10000/9 + 5x2/36 - 7x3/18 - x4/18 + x5/18
swap x2 with x0; the equation for x2 is given below
z = -x0
x1 = 1250 - x0/56 - 3x3/7 - x4/28 + 3x5/56
x2 = 1000 - 9x0/70 - 2x3/7 + x4/7 - x5/70
restore the equation for z & set x0 to 0
z = -2250 - 2x3/7 - 3x4/28 - 11x5/280
x1 = 1250 - 3x3/7 - x4/28 + 3x5/56
x2 = 1000 - 2x3/7 + x4/7 - x5/70
so x1 = 1250, x2 = 1000, x3 = 0dual problem (needs vars to ensure that y1, y2 >=0):
z = 0 - 10000y1 + 10000z1 - 30000y2 + 30000z2
y3 = 1 + 2y1 - 2z1 + 20y2 - 20z2
y4 = 1 + 7.5y1 - 7.5z1 + 5y2 - 5z2
y5 = 1 + 3y1 - 3z1 + 10y2 - 10z2
swap z1 with y4; the equation for z1 is given below
z = 4000/3 - 70000y2/3 + 70000z2/3 - 4000y4/3
z1 = 2/15 + y1 + 2y2/3 - 2z2/3 - 2y4/15
y3 = 11/15 + 56y2/3 - 56z2/3 + 4y4/15
y5 = 3/5 + 8y2 - 8z2 + 2y4/5
swap z2 with y3; the equation for z2 is given below
z = 2250 - 1250y3 - 1000y4
z1 = 3/28 + y1 + y3/28 - y4/7
z2 = 11/280 + y2 - 3y3/56 + y4/70
y5 = 2/7 + 3y3/7 + 2y4/7
note that if lines 3-5 correspond to y3-y5, (with the zi ignored)
then lines 3 & 4 intersect at (-3/28, -11/280),
while lines 3 & 5 and lines 4 & 5 intersect outside the region
one capacity constraint for each edge
two flow constraints for each vertex other than s & t
there are two since the original constraints involve equality
one flow variable for each edge
one slack variable for each edge (from above)
two slack variables for each vertex besides s & t (from above)
The dual problem thus has
one variable for each edge, representing whether it is cut
two variables for each vertex other than s & t
representing whether it lies on the same side of the cut as s
there are two since the value may (in principle?) be negative
The corresponding linear programming problem has n=5 (nonslack) variables and m=9 constraints In the table below, the first row gives the quantity to be maximized. Elsewhere, the first column gives the constraints as inequalities, the second gives the constraints in terms of slack variables, and the third gives the matrix A of coefficients, where the columns correspond respectively to the variables fsx, fsy, fxy, fxt, and fyt.
z = 0 + fsx + fsy
fsx + fsy z = 0 + fsx + fsy fsx ≤ 5 csx = 5 - fsx fsy ≤ 2 csy = 2 - fsy fxy ≤ 1 cxy = 1 - fxy fxt ≤ 2 cxt = 2 - fxt fyt ≤ 4 cyt = 4 - fyt fsx - fxy - fxt ≤ 0 cx = fxy + fxt - fsx fxy + fxt - fsx ≤ 0 dx = fsx - fxy - fxt fsy + fxy - fyt ≤ 0 cy = fyt - fsy - fxy fyt - fsy - fxy ≤ 0 dy = fsy + fxy - fyt
the dual problem (stated as a maximization problem): it has 9 (nonslack) variables and 5 constraints. Note that we'll need to find an initial feasible solution.
z = - 5csx - 2csy - cxy - 2cxt - 4cyt
fsx = -1 + csx + cx - dx
fsy = -1 + csy + cy - dy
fxy = cxy - cx + dx + cy - dy
fxt = cxt - cx + dx
fyt = cyt - cy + dy
in the original problem, swap fsx with dx; the equation for fsx is given below
z = 0 + fxy + fxt + fsy - dx
csx = 5 - fxy - fxt + dx
csy = 2 - fsy
cxy = 1 - fxy
cxt = 2 - fxt
cyt = 4 - fyt
cx = -dx
cy = fsy + fxy - fyt
dy = fyt - fsy - fxy
fsx = fxy + fxt - dx
swap fxy with dy; the equation for fxy is given below
z = 0 + fxt + fyt - dx - dy
csx = 5 + fsy - fyt - fxt + dx + dy
csy = 2 - fsy
cxy = 1 + fsy - fyt + dy
cxt = 2 - fxt
cyt = 4 - fyt
cx = - dx
cy = - dy
fsx = fyt + fxt - fsy - dx - dy
fxy = fyt - fsy - dy
swap fxt with cxt; the equation for fxt is given below
z = 2 + fyt - cxt - dx - dy
csx = 3 + fsy - fyt + cxt + dx + dy
csy = 2 - fsy
cxy = 1 + fsy - fyt + dy
cyt = 4 - fyt
cx = - dx
cy = - dy
fsx = 2 + fyt - fsy - cxt - dx - dy
fxy = fyt - fsy - dy
fxt = 2 - cxt
swap fyt with cxy; the equation for fyt is given below
z = 3 + fsy - cxy - cxt - dx
csx = 2 + cxy + cxt + dx
csy = 2 - fsy
cyt = 3 - fxy + cxy - dy
cx = - dx
cy = - dy
fsx = 3 + cxy - cxt - dx
fxy = 1 - cxy
fxt = 2 - cxt
fyt = 1 + fsy - cxy + dy
swap fsy with csy; the equation for fsy is given below
z = 5 - csy - cxy - cxt - dx
csx = 2 + cxy + cxt + dx
cyt = 3 - fxy + cxy - dy
cx = - dx
cy = - dy
fsx = 3 + cxy - cxt - dx
fsy = 2 - csy
fxy = 1 - cxy
fxt = 2 - cxt
fyt = 3 - csy - cxy + dy
the constant terms for the last 5 equations
give the flows for (s,x), (s,y), (x,y), (x,t), and (y,t).
To find an initial feasible solution in the dual problem, we start with
z = -x0
fsx = -1 + csx + cx - dx + x0
fsy = -1 + csy + cy - dy + x0
fxy = cxy - cx + dx + cy - dy + x0
fxt = cxt - cx + dx + x0
fyt = cyt - cy + dy + x0
swap x0 with fsx; the equation for x0 is given below
z = -1 - fsx + csx + cx - dx
fsy = fsx + csy - csx - cx + dx + cy - dy
fxy = 1 + fsx + cxy - csx - 2cx + 2dx + cy - dy
fxt = 1 + fsx + cxt - csx - 2cx + 2dx
fyt = 1 + fsx + cyt - csx - cx + dx - cy + dy
x0 = 1 + fsx - csx - cx + dx
swap csx with fsy; the equation for csx is given below
z = -1 - fsy + csy + cy - dy
fxy = 1 + fsy - csy + cxy - cx + dx
fxt = 1 + fsy - csy + cxt - cx + dx - cy + dy
fyt = 1 + fsy - csy + cyt - 2cy + 2dy
x0 = 1 + fsy - csy - cy + dy
csx = fsx - fsy + csy - cx + dx + cy - dy
swap csy with x0; the equation for csy is given below
z0 = - x0
fxy = cxy - cx + dx + cy - dy + x0
fxt = cxt - cx + dx + x0
fyt = cyt - cy + dy + x0
csx = 1 + fsx - cx + dx - x0
csy = 1 + fsy - cy + dy - x0
this gives the optimal value for z0, which is 0,
so we may restore the original value of z, which was
z = - 5csx - 2csy - cxy - 2cxt - 4cyt
in terms of the new basic variables, this is
z = -7 - 5fsx - 2fsy - cxy - 2cxt - 4cyt + 5cx - 5dx + 2cy - 2dy
Here we've nullified x0; doing this to the other equations gives
fxy = cxy - cx + dx + cy - dy
fxt = cxt - cx + dx
fyt = cyt - cy + dy
csx = 1 + fsx - cx + dx
csy = 1 + fsy - cy + dy
swap cx with fxy; the equation for cx is given below
z = -7 - 5fsx - 2fsy - 5fxy + 4cxy - 2cxt - 4cyt + 7cy - 7dy
fxt = fxy - cxy + cxt - cy + dy
fyt = cyt - cy + dy
csx = 1 + fsx + fxy - cxy - cy + dy
csy = 1 + fsy - cy + dy
cx = - fxy + cxy + dx + cy - dy
swap cxy with fxt; the equation for cxy is given below
z = -7 - 5fsx - 2fsy - fxy - 4fxt + 2cxt - 4cyt + 3cy - 3dy
fyt = cyt - cy + dy
csx = 1 + fsx + fxt - cxt
csy = 1 + fsy - cy + dy
cxy = fxy - fxt + cxt - cy + dy
cx = - fxt + cxt + dx
swap cxt with csx; the equation for cxt is given below
z = -5 - 3fsx - 2fsy - fxy - 2fxt - 2csx - 4cyt + 3cy - 3dy
fyt = cyt - cy + dy
csy = 1 + fxy - cy + dy
cxt = 1 + fsx + fxt - csx
cxy = 1 + fsx + fxy - csx + cxt - cy + dy
cx = 1 + fsx - fxt + dx
swap cy with fyt; the equation for cy is given below
z = -5 - 3fsx - 2fsy - fxy - 2fxt - 3fyt - 2csx - cyt
csy = 1 + fxy - cy + dy
cxt = 1 + fsx + fxt - csx
cxy = 1 + fsx + fxy - csx + cxt - cy + dy
cx = 1 + fsx - fxt + dx
cy = - fyt + cyt + dy
This gives csy = cxt = cxy = 1 = cx.
That is, the cut crosses (s,y), (x,t), and (x,y),
and x is the only other vertex on the same side of the cut as s.
x7 + 2x5 + 4x
/ \
0 x3 + 2x2 + 4
/ \ / \
0 0 2x+4 x
/ \ / \ / \ / \
0 0 0 0 4 2 0 1
which gives the following tree of vectors of values (constructed bottom up)
(7 [3√2/2 + (√2/2)i] 5i [-3√2/2 + (√2/2)i] -7 [-3√2/2 - (√2/2)i] -5i [3√2/2 - (√2/2)i])
/ \
(0 0 0 0) (7 2-i 5 2+i)
/ \ / \
(0 0) (0 0) (6 2) (1 -1)
/ \ / \ / \ / \
(0) (0) (0) (0) (4) (2) (0) (1)
since 0=0+0, 0=0-0, 0=0+0, 0=0-0, 6=4+2, 2=4-2, 1=0+1, -1=0-1,The root of this tree gives the representation. To invert this representation, we begin by thinking of its elements as coefficients of a second polynomial, and use the corresponding tree of polynomials given below
[3√2/2 - (√2/2)i]x7 - 5ix6 + [-3√2/2 - √2/2)i]x5 - 7x4 + [-3√2/2 + √2/2)i]x3 + 5ix2 + [3√2/2 + (√2/2)i]x + 7
/ \
-5ix3 - 7x2 +5ix + 7 [3√2/2 - (√2/2)i]x3 + [-3√2/2 - √2/2)i]x2 + [-3√2/2 + √2/2)i]x + [3√2/2 + (√2/2)i]
/ \ / \
-7x + 7 -5ix +5i [-3√2/2 - √2/2)i]x + [3√2/2 + (√2/2)i] [3√2/2 - (√2/2)i]x + [-3√2/2 + √2/2)i]
/ \ / \ / \ / \
7 -7 5i -5i 3√2/2 + (3√2/2)i -3√2/2 - (√2/2)i -3√2/2 + (√2/2)i 3√2/2 - (√2/2)i
which gives the following tree of vectors of values (constructed bottom up)
(0 32 0 0 0 16 0 8)
/ \
(0 24 0 4) (0 4√2 + 4√2i 0 2√2 - 2√2i)
/ \ / \
(0 14) (0 10i) (0 3√2 + √2i) (0 -3√2 + √2i)
/ \ / \ / \ / \
(7) (-7) (5i) (-5i) (3√2/2 + (√2/2)i) (-3√2/2 - (√2/2)i) (-3√2/2 + (√2/2)i) (3√2/2 - (√2/2)i)
where (showing the details for the top two levels only)Note that the root-of-unity factors in the computations above have been replaced by their reciprocals, since we are performing an inverse FFT. Finally, note that the vector in the root gives the coefficients of the original polynomial p, multiplied by n=8.
x3 + 2x2 + x - 3
/ \
2x - 3 x + 1
/ \ / \
-3 2 1 1
/ \ / \ / \ / \
-3 0 2 0 1 0 1 0
which gives the following tree of vectors of values (constructed bottom up)
(1 -3+(2+√2)i -5 -3+(-2+√2)i -3 -3+(2-√2)i -5 -3+(-2-√2)i)
/ \
(-1 -3+2i -5 -3-2i) (2 1+i 0 1-i)
/ \ / \
(-3 -3) (2 2) (1 1) (1 1)
For q(x) we have the tree of polynomials
2x3 - x + 1
/ \
1 2x - 1
/ \ / \
1 0 -1 2
/ \ / \ / \ / \
1 0 0 0 -1 0 2 0
which gives the following tree of vectors of values (constructed bottom up)
(2 (1-3√2/2)+(√2/2)i 1-3i (1+3√2/2)+(√2/2)i 0 (1+3√2/2)-(√2/2)i 1+3i (1-3√2/2)-(√2/2)i)
/ \
(1 1 1 1) (1 -1+2i -3 -1-2i)
/ \ / \
(1 1) (0 0) (-1 -1) (2 2)
The pointwise product of the two vectors is( 2 (-4+7√2/2) + (-1-7√2/2)i -5 + 15i (-4-7√2/2) + (1-7√2/2)i 0 (-4-7√2/2) + (-1+7√2/2)i -5 -15i (-4+7√2/2) + (1+7√2/2)i )and the product of the two polynomials is 2x6 + 4x5 + x3 - 7x3 + x2 + 4x - 3.
To show that the vector above is the correct representation of the polynomial, we may apply the FFT algorithm directly to the polynomial, which gives the following tree of polynomials
2x6 + 4x5 + x4 - 7x3 + x2 + 4x - 3
/ \
2x3 + x2 + x - 3 4x2 - 7x + 4
/ \ / \
x-3 2x+1 4x+4 -7
/ \ / \ / \ / \
-3 1 1 2 4 4 -7 0
and the following tree of vectors
v
/ \
(1 -4-i -5 -4+i) (1 -7i 15 7i)
/ \ / \
(-2 -4) (3 -1) (8 0) (-7 -7)
where v is the vector given by the pointwise product.
In an application, one would instead apply the inverse FFT to the vector v, which (identifying v with the corresponding polynomial) would give the following tree of polynomials
v
/ \
(-5 - 15i)x3 + (-5 + 15i)x + 2) [(-4+7√2/2) + (1+7√2/2)i]x3 + [(-4-7√2/2) + (-1+7√2/2)i]x2 +
[(-4-7√2/2) + (1-7√2/2)i]x + (-4+7√2/2) + (-1-7√2/2)i
/ \ / \
2 (-5-15i)x + (-5+15i) [(-4-7√2/2) + (-1+7√2/2)i]x + [(-4+7√2/2) + (1+7√2/2)i]x +
(-4+7√2/2) + (-1-7√2/2)i (-4-7√2/2) + (1-7√2/2)i
/ \ / \ / \ / \
2 0 -5 + 15i -5 - 15i (-4+7√2/2) + (-4-7√2/2) + (-4-7√2/2) + (-4+7√2/2) +
(-1-7√2/2)i (-1+7√2/2)i (1-7√2/2)i (1+7√2/2)i
and the following tree of vectors
(-24 32 8 -56 8 32 16 0)
/ \
(-8 32 12 -28) (-16 0 -4i 14√2-14√2i)
/ \ / \
(2 2) (-10 30i) (-8-2i 7√2-7√2i) (-8+2i -7√2-7√2i)
since 14√2-14√2i = 28ω7. The vector in the root represents the product polynomial, since it is just the sequence of the product's coefficients, multiplied by n=8.
The coefficients of A are permuted into the sequence
(-10 0 1 0 -1 0 7 0)
which is interpreted as the sequence of sequences
(-10)(0) (-1) (0) (1) (0) (7) (0)
which becomes
(-10 -10) (-1 -1) (1 1) (7 7)
which becomes
(-11 -10-i -9 -10+i) (8 1+7i -6 1-7i)
which becomes
(-3 -10-3√2+(-1+4√2)i -9-6i -10+3√2+(+1+4√2)i -19 -10+3√2+(-1-4√2)i -9+6i -10-3√2+(+1-4√2)i )
The coefficients of B are permuted into the sequence
(3 0 -6 0 0 0 8 0)
which is interpreted as the sequence of sequences
(3)(0) (0) (0) (-6) (0) (8) (0)
which becomes
(3 3) (0 0) (-6 -6) (8 8)
which becomes
(3 3 3 3) (2 -6+8i -14 -6-8i)
which becomes
(5 3-7√2+√2i 3-14i 3+7√2+√2i 1 3+7√2-√2i 3+14i 3-7√2-√2i)
The point-value representation of the product is then obtainable by multiplying corresponding elements of the two result sequences, giving
(-15 4+62√2+(-65+9√2)i -111+108i 4-62√2+(65+9√2)i -19 4-62√2+(-65-9√2)i -111-108i 4+62√2+(65-9√2)i )
Permuting this sequence and interpreting the result as n singleton sequences gives
(-15) (-19) (-111+108i) (-111-108i) (4+62√2+(-65+9√2)i) (4-62√2+(-65-9√2)i)
(4-62√2+(65+9√2)i) (4+62√2+(65-9√2)i )
Combining these sequences gives
(-34 4) (-222 216i) (8-130i 124√2+18√2i) (8+130i -124√2+18√2i)
Combining these sequences gives
(-256 220 188 -212) (16 142+142√2i -260i 106√2-106√2i)
since
-34 + i4(-222) = -34 - 222 = -256
-34 - i4(-222) = -34 + 222 = 188
4 + i3(216i) = 4 + 216 = 220
4 - i3(216i) = 4 - 216 = -212
8-130i + i4(8+130i) = 8 - 130i + 8 + 130i = 16
8-130i - i4(8+130i) = 8 - 130i - 8 - 130i = -260i
124√2+18√2i + i3(-124√2+18√2i) = 124√2 + 18√2i + 124√2i + 18√2 = 142+142√2i
124√2+18√2i - i3(-124√2+18√2i) = 124√2 + 18√2i - 124√2i - 18√2 = 106-106√2i
Combining these sequences gives
(-240 504 -72 -424 -272 -64 448 0)
since (using ω for the text's ω8)
142+142√2i = 284ω
106-106√2i = 212ω7
-256 + ω8(16) = -256 + 16 = -240
-256 - ω8(16) = -256 - 16 = -272
220 + ω7(284)ω = 220 + 284 = 504
220 - ω7(284)ω = 220 - 284 = -64
188 + ω6(-260i) = 188 + i3(-260i) = 188 - 260 = -72
188 - ω6(-260i) = 188 - i3(-260i) = 188 + 260 = 448
-212 + ω5(212)ω7 = -212 + -212 = -424
-212 - ω5(212)ω7 = -212 - -212 = 0
Then dividing by 8 gives (-30 63 -9 -53 -34 -8 56 0), which is the representation of
56x6 - 8x5 - 34x4 - 53x3 - 9x2 + 63x - 30,
which is the product of A and B.