Complexity of Bilinear Problems, lecture notes by Blaser M.

By Blaser M.

Show description

Read Online or Download Complexity of Bilinear Problems, lecture notes PDF

Best algebra books

Basic Math & Pre-Algebra For Dummies (2nd Edition)

"Basic Math & Pre-Algebra For Dummies, "2nd version, is an up to date and refreshed tackle this center starting place of math schooling. From optimistic, unfavourable, and full numbers to fractions, decimals, and percents, readers will construct the mandatory abilities to take on extra complex subject matters, resembling imaginary numbers, variables, and algebraic equations.

Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 12th International Symposium, AAECC-12 Toulouse, France, June 23–27, 1997 Proceedings

This publication constitutes the strictly refereed court cases of the twelfth overseas Symposium on utilized Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-12, held in Toulouse, France, June 1997. The 27 revised complete papers offered have been conscientiously chosen via this system committee for inclusion within the quantity.

Additional resources for Complexity of Bilinear Problems, lecture notes

Example text

On addition chains. Bulletin of the American Mathematical Society, 45:736–739, 1939. [Bsh95] Nader H. Bshouty. On the additive complexity of 2 × 2-matrix multiplication. Inform. Proc. Letters, 56(6):329–336, 1995. [Lad76] J. Laderman. A noncommutative algorithm for multiplying 3 × 3–matrices using 23 multiplications. Bull. Amer. Math. , 82:180–182, 1976. [Pan80] Victor Ya. Pan. New fast algorithms for matrix multiplication. SIAM J. Comput, 9:321–342, 1980. [Sch37] Arnold Scholz. Aufgabe 253. Mathematiker-Vereinigung, 47:41–42, 1937.

Then we still compute b1 . We can kill another β product by substituting b1 as above. After this, we still compute a0 b0 , which needs one product. However, we can approximate the tensor above by tensors of rank two. Let 1 1 t(ǫ) = (1, ǫ) ⊗ (1, ǫ) ⊗ (0, ) + (1, 0) ⊗ (1, 0) ⊗ (1, − ) ǫ ǫ t(ǫ) obviously has rank two for every ǫ > 0. The slices of t(ǫ) are 1 0 0 0 0 1 31 1 ǫ Thus t(ǫ) → t if ǫ → 0. Bini, Capovani, Lotti and Romani [BCLR79] used this effect to design better matrix multiplication algorithms.

When we replace a1 by − a0 , we kill one product. We still compute a0 b0 and β =0 α − a0 b0 + a0 b1 . Next, set a0 = 1, b0 = 0. Then we still compute b1 . We can kill another β product by substituting b1 as above. After this, we still compute a0 b0 , which needs one product. However, we can approximate the tensor above by tensors of rank two. Let 1 1 t(ǫ) = (1, ǫ) ⊗ (1, ǫ) ⊗ (0, ) + (1, 0) ⊗ (1, 0) ⊗ (1, − ) ǫ ǫ t(ǫ) obviously has rank two for every ǫ > 0. The slices of t(ǫ) are 1 0 0 0 0 1 31 1 ǫ Thus t(ǫ) → t if ǫ → 0.

Download PDF sample

Rated 4.33 of 5 – based on 7 votes