The Projective Noether Maple Package: Computing the dimension of a projective variety. (English) Zbl 0963.68235
Summary: Recent theoretical advances in elimination theory use straight-line programs as a data structure to represent multivariate polynomials. We present here the Projective Noether Package which is a Maple implementation of one of these new algorithms, yielding as a byproduct a computation of the dimension of a projective variety. Comparative results on benchmarks for time and space of several families of multivariate polynomial equation systems are given and we point out both weaknesses and advantages of different approaches.
MSC:
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | Balcázar, J. L.; Dı́az, J.; Gabarró, J., Structural Complexity. I, Texts in Theoretical Computer Science. An EATCS Series,\(2^{ nd }\) edn (1995), Springer-Verlag: Springer-Verlag Berlin · Zbl 0826.68048 |
| [2] | Berkowitz, S. J., On computing the determinant in small parallel time using a small number of processors, Inf. Process. Lett., 18, 147-150 (1984) · Zbl 0541.68019 |
| [3] | Björck, G., Functions of modulus 1 on \(Z_n\) whose Fourier transforms have constant modulus, and “cyclic \(n\) -roots”, Recent Advances in Fourier Analysis and Its Applications (Il Ciocco, 1989), volume 315 ofNATO Advance Science Institutes Series C: Mathematical and Physical Sciences (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, p. 131-140 · Zbl 0726.43004 |
| [4] | Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics, \(2^{ nd }\) edn (1997), Springer-Verlag: Springer-Verlag New York |
| [5] | Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry, volume 150 ofGraduate Texts in Mathematics (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0819.13001 |
| [6] | J.-C. Faugère; J.-C. Faugère |
| [7] | J.-C. Faugère; J.-C. Faugère |
| [8] | Fitchas, N.; Giusti, M.; Smietanski, F., Sur la complexité du théorème des zéros, Approximation and Optimization in the Caribbean, II (Havana, 1993), volume 8 ofApproximation and Optimization (1995), Peter Lang Verlag (With the collaboration of Joos Heintz, Luis Miguel Pardo, Juan Sabia and Pablo Solernó): Peter Lang Verlag (With the collaboration of Joos Heintz, Luis Miguel Pardo, Juan Sabia and Pablo Solernó) Frankfurt am Main, p. 274-329 · Zbl 0868.12008 |
| [9] | Giusti, M., Combinatorial dimension theory of algebraic varieties, J. Symb. Comput. (Special issue on computational aspects of commutative algebra), 6, 249-265 (1988) · Zbl 0697.14001 |
| [10] | Giusti, M.; Heintz, J., La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, (Eisenbud, D.; Robbiano, L., Computational Algebraic Geometry and Commutative Algebra (Cortona, 1991), volume XXXIV ofSymposia Matematica (1993), Cambridge University Press: Cambridge University Press Cambridge), 216-256 · Zbl 0829.14029 |
| [11] | M. Giusti, G. Lecerf, B. Salvy; M. Giusti, G. Lecerf, B. Salvy |
| [12] | Heintz, J., On the computational complexity of polynomials and bilinear mappings. A survey, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Menorca, 1987) (1989), Springer: Springer Berlin, p. 269-300 · Zbl 0678.68036 |
| [13] | Heintz, J.; Schnorr, C. P., Testing polynomials which are easy to compute, Logic and Algorithmic (Zürich, 1980) (1982), p. 237-254 · Zbl 0483.68043 |
| [14] | Lecerf, G., The Projective Noether Package, User’s Manual (1997), Laboratoire GAGE, École polytechnique, Palaiseau, France |
| [15] | Lecerf, G.; Schost, E., Maple Package: GB link (http://tera.medicis.polytechnique.fr/tera/soft.html) (1997), Laboratoire GAGE, École polytechnique, Palaiseau, France |
| [16] | Mehlhorn, K.; Näher, S.; Uhrig, C., Library for Efficient Datastructures and Algorithms, (http://www.mpi-sb.mpg.de/LEDA/leda.html) (1997), Max Planck Institute for Computer Science: Max Planck Institute for Computer Science Saarbrücken |
| [17] | Mulmuley, K., A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, 7, 101-104 (1987) · Zbl 0635.65040 |
| [18] | Stoß, H.-J., On the representation of rational functions of bounded complexity, Theoret. Comput. Sci., 64, 1-13 (1989) · Zbl 0679.68099 |
| [19] | Strassen, V., Berechnung und Programm. I, II, Acta Inform., 1, 320-355 (1972) · Zbl 0252.68018 |
| [20] | ibid, 2, 64-79 (1973) · Zbl 0258.68022 |
| [21] | von zur Gathen, J., Parallel arithmetic computations: a survey, Mathematical Foundations of Computer Science, 1986 (Bratislava, 1986) (1986), Springer: Springer Berlin, p. 93-112 · Zbl 0616.68037 |
| [22] | Wadler, P., Deforestation: transforming programs to eliminate trees, Theor. Comput. Sci. (Special issue of selected papers from 2’nd ESOP), 73, 231-248 (1990) · Zbl 0701.68013 |
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.
