Complexity of these computations

Outdated Archival Version

These pages are not updated anymore. They reflect the state of 2 Oct 2005. For the current production of this journal, please refer to http://www.tandfonline.com/loi/uexm20.

2.viii. Complexity of these computations

A measure of the complexity of symbolic computation is the degree of the system (number of solutions) and the dimension of the ambient variety (number of variables). Also useful are the size and time it takes to compute a (particular) Gröbner basis. The table below displays, for each small m,p the degree, d_m,p of the system, the time it takes to compute a degree reverse lexicographic Gröbner basis, the size of that basis, and number of generators. These were all computed using Singular-1.2.1 on a K6/2 300MHz processor with 256M memory running Linux. The data m,p are each linked to a Maple V.5 script that generates a Singular script that calculates a degree reverse lexicographic Gröbner basis. The Singular script is viewed by clicking on the time entry. These computations were done in local coordinates for the Grassmannian; while there are 2 more variables than the used for the verifications in Section 2.vii, the degree reverse lexicographic Gröbner basis computation is considerably faster with this choice of local coordinates.

Computing Degree Reverse Lexicographic Gröbner Bases

m,p	4,2	2,4	5,2	2,5	3,3	6,2	2,6	7,2
d_m,p	14	14	42	42	42	132	132	429
time(sec)	.04	.02	1.45	3.69	1.50	78.6	509.8	8175
Size	1.3K	1.1K	12.8K	15.4K	18.6K	202K	368K	4.58M
# Generators	20	18	47	43	43	120	127	334