nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

01.09.2023 | Preface

Further perspectives on elimination

verfasst von: Teo Mora

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 5/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Excerpt

In order to save the junior reader the trouble of referring to other works, I have put together here those elementary principles with regard to elimination, of which use has been made in the preceding pages.

G. Salmon A treatise on the higher plane curves Dublin 1852 pg.285

The device that follows, which, it may be hoped, finally eliminates from algebraic geometry the last traces of elimination-theory

A. Weil Foundations of Algebraic Geometry A.M.S. 1962 pg.31

Eliminate, eliminate, eliminate

Eliminate the eliminators of elimination theory.

S. S. Abhyankar Polynomials and Power Series (A Poem) 1970

Abhyankar’s ’eliminate’ rhythmic refrain scans the climax periods in the evolution of the approach to solving by the Computational Algebraic Geometry communities, those around conferences as MEGA, ISSAC, CoCoA, JAA and which mainly publish in journals as Commutative Algebra, JSC, AAC and also AAECC:

In 1750 Cramer [14] gave [54]

(1)

a rule for forming the terms of the common denominator of the fractions which express the values of the unknowns in a set of linear equations;

(2)

a rule for determining the sign of any individual term in the said common denominator (and, included in the rule, the notion of a “dérangement”).

(3)

A rule for obtaining the numerators from the expression for the common denominator

and in 1979 Bézout [3] introduced his [12] abbreviated method of elimination.
Anticipated by Salmon [56] who is the first to reformulate Bézout’s result as

$$\begin{aligned} \frac{U(x)V(y)-V(x)U(y)}{x-y} \end{aligned}$$

the English School (Sylvester [60‐62], Cayley [10, 12, 13], Dixon [15‐17] and Macaulay [45, 47]) introduced their method of indeterminate coefficients.
Hilbert’s fundamental paper [34] soon attracted and gave different tools for solvers as Macaulay [46, 47] (see also [48, 49]), Gunther [30‐33] and Janet [36‐39].
It is notable that when Weil [65] was expressing his hopes on elimination of elimination theory, the dominant textbooks on geometry devoted wide space to elimination [64] and determinants [66].
Abhyankar’s call to arms for eliminating the eliminators of elimination theory coincides with a period when the availability of new computational tools reoriented the Computational Algebraic Geometry communities, which included also Abhyankar himself [1], to reconsider and reformulate the results of the community inspired by Hilbert introducing Buchberger’s Gröbner bases [4‐7] (see also [22]), Faugère’s $F_4$ [20] and $F_5$ [21] (see also [18, 19]) and Gerdt’s [23, 24] and Seiler’s [57‐59] involutive bases.
While Kapur [40‐43] was reconsidering in [42] the results of Dixon [15], Cardinal’s Ph.D. Thesis [8] oriented the French school to reconsidering Bézout’s results [2, 9, 51‐53] and such investigation culminated with the introductions of RURs [55].
In the meentime, the TERA group based in École Polytechnique, Buenos Aires and Santander around Marc Giusti, Joos Heintz and Luis M.Pardo in a series of papers [25‐29, 44, 50] devised a solver with good complexity.

Hitherto I acted as a historian but now my rôle changes to that of chronicler if not even of a biased participant. As such I record in a first period two research streams, actually mutually supporting, one stabilizing, improving and extending to wider algebras what I called the gröbnerian technology, the other applying it as a panacea for solving each available research problem. In a second period, such attitude was substituted by a reaction aiming to eliminate gröbnerian technology in favour of new operational methods based on linear algebra and combinatorics; there was a different perspective in the algebraic representation of the problems to be solved, substituting the prior representation, based on polynomial ideals with a representation given by quotient algebras, expressed via a vector-space basis and multiplication matrices. I recorded and supported this new attitude under the names of Gröbner-free solving and degröbnerization but that is another story and shall be told another time. …

Nächster Artikel On restricted partitions of numbers

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abhyankar, S.S., Li, W.: On the Jacobian conjecture: a new approach via Gröbner bases. J. Pure Appl. Algebra 61, 211–222 (1989)MathSciNetMATH

Alonso, M.E., Becker, E., Roy, M.-F., Wörmann Zeroes, T.: Multiplcicities and idempotents for zerodimensional systems. Progress Math. 143, 1–16 (1996)

Bézout, E.: Théorie generale des èquations algébriques. Pierres, Paris (1771)

Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph. D. Thesis, Innsbruck (1965)

Buchberger, B.: Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleischunssystem. Aeq. Math. 4, 374–383 (1970)MATH

Buchberger, B.: Gröbner bases: an algorithmic method in polynomial ideal theory. In: Bose, N.K. (ed.) Multidimensional Systems Theory, pp. 184–232. Reider, New York (1985)

Buchberger, B.: Introduction to Göbner bases. In: Buchberger, B., Winkler, F. (eds.) Gröbner Bases and Application, pp. 3–31. Cambridge University Press, Cambridge (1998)MATH

Cardinal, J.P.: Dualité et algorithms itératifs pour la résolution de systémes polynomiaux Ph.D. Thesis Univ. Rennes I (1993)

Cardinal, J.P., Mourrain, B.: Algebraic approach of residues and applications. Lect. Notes Appl. Math. 32, 189–210 (1999)MathSciNetMATH

10.

Cayley, A.: On the theory of elimination. Cambr. Dublin Math. J. 3, 116–120 (1848)

11.

Cayley, A.: Researches on the partition of numbers. Philos. Trans. R. Soc. London 146, 127–140 (1856)

12.

Cayley, A., Cayley, A.: Note sur la méthode d’élimination de Bezout. J. Reine Und Ang. Math. 53, 366–367 (1857)MATH

13.

Cayley, A.: A fourth memory upon quantics. Philos. Trans. R. Soc. London 148, 415–427 (1858)

14.

Cramer, D.: Introduction a l’analyse des lignes Courbes Algebriques. Geneve (2022)

15.

Dixon, A.L.: On a form of the eliminant of two quatics. Proc. London Math. Soc. 6, 468–78 (1908)MathSciNetMATH

16.

Dixon, A.L.: The eliminant of three quatics in two independent variables. Proc. London Math. Soc. 7, 49–69 (1908)

17.

Dixon, A.L.: Some results in the theory of elimination. London R. Soc. Proc. 82, 468–78 (1909)

18.

Eder, C., Perry, J.: F5C: A variant of Faugère’s $F_5$ Algorithm with reduced Gröbner bases. J. Symb. Comp. 45, 1442–1450 (2010)MATH

19.

Eder, C., Perry, J.: Signature-based Algoritms to compute Gröbner bases. Proc. ISSAC’11 , 99–106, ACM (2011)

20.

Faugère, J.-C.: A new efficient algorithm for computating Gröbner bases ($F_4$). J. Pure Appl. Algebra 139, 61–88 (1999)MathSciNetMATH

21.

Faugère, J.-C.: A new efficient algorithm for computating Gröbner bases without reduction to zero ($F_5$). Proc. ISSAC 2002. 75–83, ACM (2002)

22.

Gebauer, R., Möller, H.M.: On an Installation of Buchbgerger’s Algorithm. J. Symb. Comp. 6, 275–286 (1988)MATH

23.

Gerdt, V.P., Blinkov, Y.A.: Involutive bases of polynomial ideals. Math. Comp. Simul. 45, 543–560 (1998)MathSciNetMATH

24.

Gerdt, V.P., Blinkov, Y.A.: Minimal involutive bases. ACM SIGSAM Bull. 31, 44 (1997)MATH

25.

Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M.: When polynomial equation systems can be “solved’’ fast? L. N. Comp. Sci. 948, 205–231 (1995)MathSciNetMATH

26.

Giusti, M., Heintz, J., Morais, J.E., Morgensten, J., Pardo, L.M.: Straight-line programs in geometric elimination theory. J. Pure Appl. Algebra 124, 101–146r (1998)MathSciNetMATH

27.

Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Pardo, L.M.: Montaña, Lower bounds for diophantine approximation. J. Pure Appl. Algebra 117–118, 277–311 (1997)MATH

28.

Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M.: Le rôle des structures de données dans les problèmes d’élimination. C. R. Acad. Sci. Paris 325, 1223–1228 (1997)MathSciNetMATH

29.

Giusti, M., Lecerf, G., Salvy, B.: A Gröbner Free Alternative for Polynomial System Solving. J. Complex. 17, 154–211 (2001)MATH

30.

Gunther, N.: Sur les caractéristiques des systémes d’équations aux dérivées partialles. C. R. Acad. Sci. Paris 156, 1147–1150 (1913)MATH

31.

Gunther, N.: Sur la forme canonique des equations algébriques. C. R. Acad. Sci. Paris 157, 577–580 (1913)MATH

32.

Gunther, N.: Sur la théorie générale des systèmes d’équations aux dérivées partielles. C. R. Acad. Sci. Paris 158, 853–856 (1914)MATH

33.

Gunther, N.: Sur les modules des formes algébriques Trudy Tbilis. Mat. Inst. 9, 97–206 (1941)MathSciNet

34.

Hilbert, D.: Uber die Theorie der algebraicschen Formen. Math. Ann. 36, 473–534 (1890)MathSciNetMATH

35.

Jacob, C.G.: De eliminatione variabilis e duabus aequationibus algebraicis. J. die reine und Angew. Math. 15, 101–124 (1836)MathSciNetMATH

36.

Janet, M.: Sur les systèmes d’équations aux dérivées partielles. J. Math. Pure Appl. 3, 65–151 (1920)MATH

37.

Janet, M.: Les modules de formes algébraiques et la théorie générale des systèmes diffèrentielles. Ann. Éc. Norm. $3^e$série 41 27–65, (1924)

38.

Janet, M.: Les systèmes d’équations aux dérivées partielles. Mémorial Sci. Math. XXI, Gauthiers-Villars (1927)

39.

Janet, M.: Leçons sur les systèmes d’équations aux dérivées partielles. Gauthiers-Villars. (1929)

40.

Kapur, D., Chtcherba, A.D.: Conditions for exact resultants using the dixon resultant formulation. Proc. ISSAC 2000 62–70, ACM (2000)

41.

Kapur, D., Chtcherba, A.D.: On the efficiency and oprimality of Dixon-based resultant method. Proc. ISSAC 2002, 29–36, ACM (2002)

42.

Kapur, D., Saxena, T., Yang, L.: Algebraic and geometric reasoning using Dixon resultants. Proc. ISSAC 94, 99–36, ACM (1994)

43.

Kapur, D., Saxena, T.: Extraneus factors in the Dixon resultant formulation. Proc. ISSAC 97, 141–148, ACM (1997)

44.

Lecerf, G.: Une alternative aux méthodes de réécriture pour résolution des systémes algébriques Ph.D. Thesis, École Polytechnique (2001)

45.

Macaulay, F.S.: Some formulae in elimination. Proc. London Math. Soc. 1(35), 3–27 (1903)MathSciNetMATH

46.

Macaulay, F.S.: On the resolution of a given modular system into primary systems including some properties of Hilbert numbers. Math. Ann. 74, 66–121 (1913)MathSciNetMATH

47.

Macaulay, F.S.: The Algebraic Theory of Modular Systems. Cambridge University Press, Cambridge (1916)MATH

48.

Macaulay, F.S.: Some properties of enumeration in the theory of modular systems. Proc. London Math. Soc. 26, 531–555 (1927)MathSciNetMATH

49.

Macaulay, F.S.: Modern algebra and polynomial ideals. Proc. Cambr. Philos. Soc. 30, 27–46 (1934)MathSciNetMATH

50.

Morais, J.E.: Resolución eficaz de systemas de ecuaciones polinomiales, Ph. D. Thesis, Univ. Cantabria, Santander (1997)

51.

Mourrain, B.: A New Criterion for Normal Form Algorithms. In: Fossorier M., Imai H., Lin S., Poli A. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 1999. Lecture Notes in Computer Science, vol 1719. Springer, Berlin, Heidelberg (1999)

52.

Mourrain, B.: Bezoutian and quotient ring structure. J. Symb. Comp. 39, 397–415 (2005)MathSciNetMATH

53.

Mourrain, B., Trebuchet, P.: Solving projective complete intersection faster, Proc. ISSAC’00 234–241, ACM (2000)

54.

Muir, T.: The Theory of Determinants in the Historical Order of Development. MacMillan, London (1906)

55.

Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation. J. AAECC 9, 433–461 (1999)MathSciNetMATH

56.

Salmon, G.: A treatise on the higher plane curves Dublin (1852)

57.

Seiler, W.M.: A combinatorial approach to involution and $\delta$-regularity I: involutive bases in polynomial algebras of solvable type. J. AAECC 20(3–4), 207–259 (2009)MathSciNetMATH

58.

Seiler, W.M.: A combinatorial approach to involution and $\delta$-regularity II: structure analysis of polynomial modules with Pommaret bases. J. AAECC 20(3–4), 261–338 (2009)MathSciNetMATH

59.

Seiler, W.M.: Involution: The Formal Theory of Differential Equations and its Applications. Springer, New York (2010)MATH

60.

Sylvester, J.J.: A method of determining by mere inspection the derivatives from two equations of any degree. Philos. Magaz. 16, 132–135 (1840)

61.

Sylvester, J.J.: Memoir on the dialytic method of elimination. Part I. Philos. Magaz. 31, 534–539 (1842)

62.

Sylvester, J.J.: On a theory of the syzygietic relations of two rational integral functions, comprising an application to the theory of Sturm’s functions, and that of the greatest algebraic common measure. Philos. Trans. R. Soc. London 148, 407–548 (1853)

63.

Sylvester, J.J.: On the partition of numbers. Quart. J. Pure Appl. Math. 1, 141–152 (1855)

64.

van der Waerden, B.L.: Modern Algebra. Ungar, New York (1949)

65.

Weil, A.: Foundations of Algebraic Geometry. American Mathematical Society, Rhode Island (1962)MATH

66.

Zariski, O., Samuel, P.: Commutative Algebra. Van Nostrand, New York (1958)MATH

Titel: Further perspectives on elimination
verfasst von: Teo Mora
Publikationsdatum: 01.09.2023
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 5/2023
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-023-00618-2

Springer Professional

Excerpt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Premium Partner