Lectures on the complexity of bilinear problems

This book is based on lectures given by the author at the University of Zürich. It presents relatively recent results in a unified and well organized way, and it provides a direct and fast introduction to the theory of algebraic complexity of bilinear mappings. It will be very useful for graduate students and researchers who wish to get a quick orientation on this topic, and it will be very much appreciated by those who want to teach a course Complexity of bilinear problems. Bilinear mappings are described by tensors which are up to scaling in a one-one correspondence with bilinear algorithms computing the bilinear mapping. Since the rank of a tensor and the algebraic complexity of the corresponding bilinear mapping are linearly related it would be sufficient to compute the rank which is, however, usually a difficult problem. This is developed in Chapter 1, and Chapter 2 deals with elementary properties of rank and with related notions. A very general example of a bilinear mapping is multiplication in algebras with the important special cases of matrix multiplication and multiplication of polynomials. Chapter 3 studies matrix multiplication. Let \(M_ K(n)\) be the number of arithmetic operations that suffice to compute the product of two arbitrary (n,n)-matrices over the field K and define the exponent of matrix multiplication over K by \(\omega (K)=\inf \{c:\) \(M_ K(n)=O(n^ c)\}\). It turns out that \(\omega\) depends at most on the characteristic of K, i.e. \(\omega (K)=\omega (K')\) if K and K' have the same characteristic. Regarding the computation of \(\omega\) the author begins with an estimation by the logarithm of the rank of the tensor which corresponds to matrix multiplication (understood as bilinear mapping). A better result can be achieved by replacing the rank by the border rank. A further improvement comes from the fact that the border rank is not additive with respect to direct sums of tensors and in particular from Schönhage's \(\tau\)-theorem. The next chapter is devoted to multiplication in algebras. It contains the lower bound theorem by A. Adler and V. Strassen which says that the complexity of the multiplication tensor of a given algebra A is greater than or equal to 2 dim A-m(A) where m(A) is the (always finite) number of maximal two-sided ideals of A. The next topic of this chapter are algebras of minimal rank (those whose multiplication tensor has rank 2 dim A-m(A)). Division algebras and commutative algebras of minimal rank are characterized. The set of all optimal bilinear algorithms for computing a given bilinear mapping turns out to be a variety. The varieties of multiplication in algebras and multiplication of polynomials and the proper isotropy groups of these mappings (which act as transformation groups on the corresponding varieties) are determined.

Recommendations

Cited in

(30)

This page was built for publication: Lectures on the complexity of bilinear problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1087014)