Invariant and geometric aspects of algebraic complexity theory. I. (English) Zbl 0735.68033
The author investigates the following problem: What is the minimum number, denoted by \(L_ +(v_ 1,v_ 2,\dots,v_ t\mid x_ 1,x_ 2,\dots,x_ n)\), of those additive steps required to compute a given set \(v=(v_ 1,\dots,v_ t)\) of \(t\) linear forms of variables \(x_ 1,x_ 2,\dots,x_ n\).
He establishes a natural connection of this question with some problems of graph theory, projective geometry, algebraic geometry and recent results in application of combinatorics to classical invariant theory [cf. P. Doubilet, G. C. Rota and J. Stein, Stud. Appl. Math. 53, 185-216 (1974; Zbl 0426.05009)]. There are elementary motive examples in the paper. In the following paper the author intends to consider some interesting questions arisen in his investigations in this field.
He establishes a natural connection of this question with some problems of graph theory, projective geometry, algebraic geometry and recent results in application of combinatorics to classical invariant theory [cf. P. Doubilet, G. C. Rota and J. Stein, Stud. Appl. Math. 53, 185-216 (1974; Zbl 0426.05009)]. There are elementary motive examples in the paper. In the following paper the author intends to consider some interesting questions arisen in his investigations in this field.
Reviewer: N.Osetinski
MSC:
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 15A75 | Exterior algebra, Grassmann algebras |
| 14L24 | Geometric invariant theory |
| 68W30 | Symbolic computation and algebraic computation |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 51A20 | Configuration theorems in linear incidence geometry |
Citations:
Zbl 0426.05009References:
| [1] | Borodin, A.; Munro, I., (The Computational Complexity of Algebraic and Numerical Problems (1975), Elsevier: Elsevier New York) · Zbl 0404.68049 |
| [2] | Bruns, W.; Vetter, U., Determinantal rings, (Lecture Notes in Mathematics (1988), Springer: Springer Heidelberg), 1327 · Zbl 0673.13006 |
| [3] | Cooley, J. M.; Tukey, J. W., An algorithm for the machine calculation of complex Fourier series, Math. Comput., 19, 297-302 (1965) · Zbl 0127.09002 |
| [4] | Dieudonne, J. A., Une propriété des racines de ľunité, Revista de la Union Matematica Argentina, 25 (1970) · Zbl 0229.12002 |
| [5] | Doubilet, P.; Rota, G. C.; Stein, J., Foundations of combinatorics IX: Foundations of combinatorial methods in invariant theory, Study Appl. Math., 53, 185-216 (1974) · Zbl 0426.05009 |
| [6] | Garey, M. R.; Johnson, D. S., (Compulability and Intractability (1979), Freeman: Freeman New York) · Zbl 0411.68039 |
| [7] | Heintz, J.; Sieveking, M., Lower bounds for polynomials with algebraic coefficients, Theoretical Computer Science, 11, 321-330 (1980) · Zbl 0452.68051 |
| [8] | Kaminski, M.; Kirkpatrick, D.; Bshouty, N., Addition requirements for matrix and transposed matrix products, J. Algorithms, 9, 354-372 (1988) · Zbl 0653.65032 |
| [9] | Kirkpatrick, D. G., On the number of additions necessary to compute certain functions, (Proceedings of the 4th ACM Symp. on Theory of Computing (1972)), 94-99 |
| [10] | Morgenstern, J., (On Linear Algorithms in Theory of Machines and Computations (1971), Academic Press: Academic Press New York), 59-66 · Zbl 0266.94019 |
| [11] | Morgenstern, J., Algorithmes linéaires tangents et complexité, Compte Rendu de ľAcadémie des Sciences, 277, 367-370 (1973) · Zbl 0266.68021 |
| [12] | Morgenstern, J., Note on a lower bound of the linear complexity of the Fast Fourier Transform, J. Assoc. Comput. Mach., 20, 305-309 (1973) · Zbl 0258.65120 |
| [13] | Morgenstern, J., Compexité linéaire de Calcul, (Thèse ďEtat du 27 Novembre 1978 (1978), Université de Nice) |
| [14] | Northcott, D. G., (Finite Free Resolution (1976), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0328.13010 |
| [15] | Pippenger, N., Superconcentrators, SIAM J. Computing, 6, 298-304 (1978) · Zbl 0361.05035 |
| [16] | Rota, G. C., Théorie combinatoire des invariants classiques 1976, (Séries de Mathématiques Pures et Appliquées (1976), IRMA: IRMA Strasbourg) |
| [17] | Rota, G. C., (Combinatorial Theory and Invariant Theory (1971), Bowdoin College: Bowdoin College Maine) |
| [18] | Shafarevitch, I. R., (Algebraic Geometry (1977), Springer: Springer Heidelberg) · Zbl 0362.14001 |
| [19] | Strassen, V., Vermeidung von Divisionen, J. Reine Ange. Math., 264 (1976) · Zbl 0294.65021 |
| [20] | Strassen, V., Die berechnungskomplexität von elementarsymmetrischen funktionen, Numerische Mathematik, 20, 238-251 (1973) · Zbl 0251.65036 |
| [21] | Sturmfels, B.; White, W., Symbolic computations in geometry, (IMA Preprint series, 389 (1988), University of Minnesota) |
| [22] | Valiant, L. G., Graph theoretic arguments in low-level complexity, Lecture Notes in Computer Science, 53 (1977) · Zbl 0384.68046 |
| [23] | White, N., Multilinear Cayley factorization, J. Symbolic Computation, 11, 421-438 (1990) · Zbl 0747.15009 |
| [24] | Winograd, S., On the number of mutliplications necessary to compute certain functions, Communication on Pure and Applied Mathematics, 23 (1970) · Zbl 0191.15804 |
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.
