Semisimple algebras of almost minimal rank over the reals. (English) Zbl 1194.68121
Summary: A famous lower bound for the bilinear complexity of the multiplication in associative algebras is the Alder-Strassen bound [A. Alder and V. Strassen, Theor. Comput. Sci. 15, 201–211 (1981; Zbl 0464.68045)]. Algebras for which this bound is tight are called algebras of minimal rank. After 25 years of research, these algebras are now well understood. Here we start the investigation of the algebras for which the Alder-Strassen bound is off by one. As a first result, we completely characterize the semisimple algebras over \(\mathbb R\) whose bilinear complexity is by one larger than the Alder-Strassen bound. Furthermore, we characterize all algebras \(A\) (with radical) of minimal rank plus one over \(\mathbb R\) for which \(A/\text{rad}\,A\) has minimal rank plus one. The other possibility is that \(A/\text{rad}\,A\) has minimal rank. For this case, we only present a partial result.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 16Z05 | Computational aspects of associative rings (general theory) |
| 16K20 | Finite-dimensional division rings |
| 03D15 | Complexity of computation (including implicit computational complexity) |
Citations:
Zbl 0464.68045References:
| [1] | Alder, A.; Strassen, V., On the algorithmic complexity of associative algebras, Theoret. Comput. Sci., 15, 201-211 (1981) · Zbl 0464.68045 |
| [2] | Alekseyev, Valery B., On the complexity of some algorithms for matrix multiplication, J. Algorithms, 6, 1, 71-85 (1985) · Zbl 0577.68059 |
| [3] | Markus Bläser, Untere Schranken für den Rang assoziativer Algebren. Dissertation, Universität Bonn, 1999; Markus Bläser, Untere Schranken für den Rang assoziativer Algebren. Dissertation, Universität Bonn, 1999 |
| [4] | Bläser, Markus, Lower bounds for the bilinear complexity of associative algebras, Comput. Complexity, 9, 73-112 (2000) · Zbl 0970.68069 |
| [5] | Bläser, Markus, On the complexity of the multiplication of matrices of small formats, J. Complexity, 19, 43-60 (2003) · Zbl 1026.68062 |
| [6] | Bläser, Markus, A complete characterization of the algebras of minimal bilinear complexity, SIAM J. Comput., 34, 2, 277-298 (2004) · Zbl 1087.68037 |
| [7] | Bshouty, Nader H., Multiplicative complexity of direct sums of quadratic systems, Linear Algebra Appl., 215, 182-255 (1995) · Zbl 0820.15015 |
| [8] | Büchi, Werner; Clausen, Michael, On a class of primary algebras of minimal rank, Linear Algebra Appl., 69, 249-268 (1985) · Zbl 0574.16011 |
| [9] | Bürgisser, Peter; Clausen, Michael; Amin Shokrollahi, M., Algebraic Complexity Theory (1997), Springer · Zbl 1087.68568 |
| [10] | de Groote, Hans F., Characterization of division algebras of minimal rank and the structure of their algorithm varieties, SIAM J. Comput., 12, 101-117 (1983) · Zbl 0513.68039 |
| [11] | de Groote, Hans F.; Heintz, Joos, Commutative algebras of minimal rank, Linear Algrbra Appl., 55, 37-68 (1983) · Zbl 0527.68027 |
| [12] | Heintz, Joos; Morgenstern, Jacques, On associative algebras of minimal rank, (Proc. 2nd Applied Algebra and Error Correcting Codes Conf. (AAECC). Proc. 2nd Applied Algebra and Error Correcting Codes Conf. (AAECC), Lecture Notes in Comput. Sci., vol. 228 (1986), Springer), 1-24 · Zbl 0601.16018 |
| [13] | Strassen, Volker, Algebraic complexity theory, (van Leeuwen, J., Handbook of Theoretical Computer Science Vol. A (1990), Elsevier Science Publishers B.V), 634-672 · Zbl 0900.68247 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
