Is Matrix Inversion an N 3 Process in Software Include pdf417 2d barcode in Software Is Matrix Inversion an N 3 Process

How to generate, print barcode using .NET, Java sdk library control with example project source code free download:
2.11 Is Matrix Inversion an N 3 Process using barcode printer for software control to generate, create barcode pdf417 image in software applications. Java Projects We close this chapt Software pdf417 2d barcode er with a little entertainment, a bit of algorithmic prestidigitation that probes more deeply into the subject of matrix inversion. We start with a seemingly simple question:. 2.11 Is Matrix Inversion an N 3 Process How many individual Software pdf417 multiplications does it take to perform the matrix multiplication of two 2 2 matrices, a00 a10 a01 a11 b00 b10 b01 b11 c D 00 c10 c01 c11 (2.11.1).

Eight, right Here they are written explicitly: c00 D a00 c01 D a00 c10 D a10 c11 D a10 b00 C a01 b01 C a01 b00 C a11 b01 C a11 b10 b11 b10 b11. (2.11.2).

Do you think that o ne can write formulas for the c s that involve only seven multiplications (Try it yourself, before reading on.) Such a set of formulas was, in fact, discovered by Strassen [1]. The formulas are Q0 .

a00 C a11 / .b00 C b11 /. Q1 .a10 C a11 / b PDF417 for None 00 Q2 a00 .b01 b11 / Q3 a11 .

b00 C b10 / (2.11.3) Q4 .

a00 C a01 / b11 Q5 . a00 C a10 / .b00 C b01 / Q6 .

a01 in terms of which c00 D Q0 C Q3 c10 D Q1 C Q3 c01 D Q2 C Q4 c11 D Q0 C Q2 Q4 C Q6 (2.11.4) Q1 C Q5 a11 / .

b10 C b11 /. What s the use of t his There is one fewer multiplication than in equation (2.11.2), but many more additions and subtractions.

It is not clear that anything has been gained. But notice that in (2.11.

3) the a s and b s are never commuted. Therefore (2.11.

3) and (2.11.4) are valid when the a s and b s are themselves matrices.

The problem of multiplying two very large matrices (of order N D 2m for some integer m) can now be broken down recursively by partitioning the matrices into quarters, sixteenths, etc. And note the key point: The savings is not just a factor 7/8 ; it is that factor at each hierarchical level of the recursion. In total it reduces the process of matrix multiplication to order N log2 7 instead of N 3 .

What about all the extra additions in (2.11.3) (2.

11.4) Don t they outweigh the advantage of the fewer multiplications For large N , it turns out that there are six times as many additions as multiplications implied by (2.11.

3) (2.11.4).

But, if N is very large, this constant factor is no match for the change in the exponent from N 3 to N log2 7 .. 2. Solution of Linear Algebraic Equations With this fast ma trix multiplication, Strassen also obtained a surprising result for matrix inversion [1]. Suppose that the matrices a00 a01 c00 c01 and (2.11.

5) a10 a11 c10 c11 are inverses of each other. Then the c s can be obtained from the a s by the following operations (compare equations 2.7.

11 and 2.7.25): R0 D Inverse.

a00 / R1 D a10 R0 R2 D R0 a01 R3 D a10 R2 R4 D R3 a11 R5 D Inverse.R4 / c01 D R2 c10 D R5 R6 D R2 c00 D R0 c11 D R5 R5 R1 c10 R6 (2.11.

6). In (2.11.6) the in PDF-417 2d barcode for None verse operator occurs just twice.

It is to be interpreted as the reciprocal if the a s and c s are scalars, but as matrix inversion if the a s and c s are themselves submatrices. Imagine doing the inversion of a very large matrix, of order N D 2m , recursively by partitions in half. At each step, halving the order doubles the number of inverse operations.

But this means that there are only N divisions in all! So divisions don t dominate in the recursive use of (2.11.6).

Equation (2.11.6) is dominated, in fact, by its 6 multiplications.

Since these can be done by an N log2 7 algorithm, so can the matrix inversion! This is fun, but let s look at practicalities: If you estimate how large N has to be before the difference between exponent 3 and exponent log2 7 D 2:807 is substantial enough to outweigh the bookkeeping overhead, arising from the complicated nature of the recursive Strassen algorithm, you will nd that LU decomposition is in no immediate danger of becoming obsolete. However, the fast matrix multiplication routine itself is beginning to appear in libraries like BLAS, where it is typically used for N & 100. Strassen s original result for matrix multiplication has been steadily improved.

The fastest currently known algorithm [2] has an asymptotic order of N 2:376 , but it is not likely to be practical to implement it. If you like this kind of fun, then try these: (1) Can you multiply the complex numbers .aCi b/ and .

cCid / in only three real multiplications [Answer: See 5.5.] (2) Can you evaluate a general fourth-degree polynomial in x for many different values of x with only three multiplications per evaluation [Answer: See 5.

1.]. CITED REFERENCES AN D FURTHER READING: Strassen, V. 1969, Gaussian Elimination Is Not Optimal, Numerische Mathematik, vol. 13, pp.

354 356.[1].
Copyright © . All rights reserved.