×

Symmetry in multivariate ideal interpolation. (English) Zbl 1525.13041

Summary: An interpolation problem is defined by a set of linear forms on the (multivariate) polynomial ring and values to be achieved by an interpolant. For Lagrange interpolation the linear forms consist of evaluations at some nodes, while Hermite interpolation also considers the values of successive derivatives. Both are examples of ideal interpolation in that the kernels of the linear forms intersect into an ideal. For an ideal interpolation problem with symmetry, we address the simultaneous computation of a symmetry adapted basis of the least interpolation space and the symmetry adapted H-basis of the ideal. Beside its manifest presence in the output, symmetry is exploited computationally at all stages of the algorithm. For an ideal invariant, under a group action, defined by a Gröbner basis, the algorithm allows to obtain a symmetry adapted basis of the quotient and of the generators. We shall also note how it applies surprisingly but straightforwardly to compute fundamental invariants and equivariants of a reflection group.

MSC:

13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
13A50 Actions of groups on commutative rings; invariant theory
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ariki, S.; Terasoma, T.; Yamada, H., Higher Specht polynomials, Hiroshima Math. J., 27, 177-188 (1997) · Zbl 0886.20009
[2] Atkinson, K.; Han, W., Spherical Harmonics and Approximations on the Unit Sphere: An Introduction, Lecture Notes in Mathematics, vol. 2044 (2012), Springer: Springer Heidelberg · Zbl 1254.41015
[3] Benson, C.; Grove, L., Finite Reflection Groups, Graduate Texts in Mathematics, vol. 99 (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0579.20045
[4] Berthomieu, J.; Boyer, B.; Faugère, J. C., Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences, J. Symb. Comput., 83, 36-67 (2017) · Zbl 1453.68222
[5] Birkhoff, G., The algebra of multivariate interpolation, (Constructive Approaches to Mathematical Models (1979)), 345-363 · Zbl 0463.41001
[6] Buchberger, B., A theoretical basis for the reduction of polynomials to canonical forms, ACM SIGSAM Bull., 10, 19-29 (1976)
[7] Chevalley, C., Invariants of finite groups generated by reflections, Am. J. Math., 77, 778-782 (1955) · Zbl 0065.26103
[8] Collowald, M.; Hubert, E., A moment matrix approach to computing symmetric cubatures (2015)
[9] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics (2015), Springer: Springer Cham · Zbl 1335.13001
[10] Cox, D. A.; Little, J.; O’shea, D., Using Algebraic Geometry, Graduate Texts in Mathematics, vol. 185 (2006)
[11] De Boor, C., Gauss elimination by segments and multivariate polynomial interpolation, (Approximation and Computation: A Festschrift in Honor of Walter Gautschi (1994), Springer), 1-22 · Zbl 0851.65008
[12] De Boor, C.; Ron, A., On multivariate polynomial interpolation, Constr. Approx., 6 (1990) · Zbl 0719.41006
[13] De Boor, C.; Ron, A., The least solution for the polynomial interpolation problem, Math. Z., 210 (1992) · Zbl 0735.41001
[14] Fassino, C.; Möller, H., Multivariate polynomial interpolation with perturbed data, Numer. Algorithms, 71, 273-292 (2016) · Zbl 1334.65026
[15] Fässler, A.; Stiefel, E., Group theoretical methods and their applications (1992) · Zbl 0769.20002
[16] Faugere, J. C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symb. Comput., 16, 329-344 (1993) · Zbl 0805.13007
[17] Faugère, J. C.; Mou, C., Sparse FGLM algorithms, J. Symb. Comput., 80, 538-569 (2017) · Zbl 1404.13031
[18] Faugère, J. C.; Rahmany, S., Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases, (Proc. ISSAC 2009 (2009), ACM), 151-158 · Zbl 1237.13052
[19] Faugere, J. C.; Svartz, J., Grobner bases of ideals invariant under a commutative group: the non-modular case, (Proc. ISSAC 2013 (2013), ACM), 347-354 · Zbl 1360.68931
[20] Gatermann, K., Symbolic solution of polynomial equation systems with symmetry, (ISSAC’90 (1990), ACM-Press: ACM-Press Tokyo, Japan), 112-119
[21] Gatermann, K., Linear representations of finite groups and the ideal theoretical construction of G-invariant cubature formulas, (Numerical Integration. Numerical Integration, Bergen, 1991. Numerical Integration. Numerical Integration, Bergen, 1991, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 357 (1992), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 25-35 · Zbl 0751.41025
[22] Gatermann, K., Computer Algebra Methods for Equivariant Dynamical Systems, Lecture Notes in Mathematics, vol. 1728 (2000), Springer-Verlag: Springer-Verlag Berlin · Zbl 0944.65131
[23] Gatermann, K.; Guyard, F., Gröbner bases, invariant theory and equivariant dynamics, J. Symb. Comput., 28, 275-302 (1999) · Zbl 0939.68171
[24] Gatermann, K.; Parrilo, P., Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 192, 95-128 (2004) · Zbl 1108.13021
[25] Geramita, A., Inverse systems of fat points: Waring’s problem, secant varieties of Veronese varieties and parameter spaces for Gorenstein ideals, (The Curves Seminar at Queen’s, Vol. X. The Curves Seminar at Queen’s, Vol. X, Kingston, ON, 1995. The Curves Seminar at Queen’s, Vol. X. The Curves Seminar at Queen’s, Vol. X, Kingston, ON, 1995, Queen’s Papers in Pure and Appl. Math., vol. 102 (1996), Queen’s Univ.: Queen’s Univ. Kingston, ON) · Zbl 0864.14031
[26] Golub, G.; Van Loan, C., Matrix Computations (1996) · Zbl 0865.65009
[27] Hubert, E.; Labahn, G., Rational invariants of scalings from Hermite normal forms, (Proc. ISSAC 2012 (2012), ACM), 219-226 · Zbl 1323.68605
[28] Hubert, E.; Labahn, G., Scaling invariants and symmetry reduction of dynamical systems, Found. Comput. Math., 13, 479-516 (2013) · Zbl 1284.34045
[29] Hubert, E.; Labahn, G., Computation of the invariants of finite abelian groups, Math. Comput., 85, 3029-3050 (2016) · Zbl 1361.13005
[30] Hubert, E.; Rodriguez Bazan, E., Algorithms for fundamental invariants and equivariants (of finite groups), Math. Comput., 91, 337, 2459-2488 (2022) · Zbl 07574510
[31] Iarrobino, A.; Kanev, V., Power Sums, Gorenstein Algebras, and Determinantal Loci, Lecture Notes in Mathematics, vol. 1721 (1999), Springer-Verlag: Springer-Verlag Berlin · Zbl 0942.14026
[32] Javanbakht, M.; Sauer, T., Numerical computation of H-bases, BIT Numer. Math., 59, 417-442 (2019) · Zbl 1420.13061
[33] Kane, R., Reflection Groups and Invariant Theory, CMS Books in Mathematics, vol. 5 (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0986.20038
[34] Krick, T.; Szanto, A.; Valdettaro, M., Symmetric interpolation, exchange lemma and Sylvester sums, Commun. Algebra, 45, 3231-3250 (2017) · Zbl 1393.13052
[35] Macaulay, F., The Algebraic Theory of Modular Systems, Cambridge Tracts in Mathematics and Mathematical Physics, vol. 19 (1916) · JFM 46.0167.01
[36] Marinari, M.; Möller, H.; Mora, T., Gröbner bases of ideals given by dual bases, (ISSAC’91 (1991), ACM), 55-63 · Zbl 0925.13011
[37] Möller, H.; Buchberger, B., The construction of multivariate polynomials with preassigned zeros, (European Computer Algebra Conference (1982)) · Zbl 0549.68026
[38] Möller, H.; Sauer, T., H-bases for polynomial interpolation and system solving, Adv. Comput. Math., 12, 335-362 (2000) · Zbl 0943.65059
[39] Mourrain, B., Fast algorithm for border bases of Artinian Gorenstein algebras, (ISSAC’17 (2017), ACM Press: ACM Press Kaiserslautern, Germany), 333-340 · Zbl 1458.13036
[40] Noonburg, V., A neural network modeled by an adaptive Lotka-Volterra system, SIAM J. Appl. Math., 49, 1779-1792 (1989) · Zbl 0684.92008
[41] Pistone, G.; Riccomagno, E.; Wynn, H., Algebraic Statistics: Computational Commutative Algebra in Statistics (2000), Chapman and Hall/CRC
[42] Pistone, G.; Wynn, H., Generalised confounding with Gröbner bases, Biometrika, 83, 653-666 (1996) · Zbl 0928.62060
[43] Riener, C.; Safey El Din, M., Real root finding for equivariant semi-algebraic systems, (Proc. ISSAC 2018 (2018), ACM), 335-342 · Zbl 1467.14140
[44] Riener, C.; Theobald, T.; Andrén, L. J.; Lasserre, J. B., Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res., 38, 122-141 (2013) · Zbl 1291.90167
[45] Rodriguez Bazan, E.; Hubert, E., Symmetry preserving interpolation, (Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation (2019), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 34-41 · Zbl 1467.41001
[46] Rodriguez Bazan, E.; Hubert, E., Ideal interpolation, H-bases and symmetry, (Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (2020), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 402-409 · Zbl 07300098
[47] Rodriguez Bazan, E.; Hubert, E., Multivariate interpolation: preserving and exploiting symmetry, J. Symb. Comput., 107, 1-22 (2021) · Zbl 1479.41002
[48] Sauer, T., Gröbner bases, H-bases and interpolation, Trans. Am. Math. Soc., 353, 2293-2308 (2001) · Zbl 0967.65005
[49] Sauer, T., Prony’s method in several variables, Numer. Math., 136 (2017) · Zbl 1377.65048
[50] Sauer, T., Prony’s method in several variables: symbolic solutions by universal interpolation, J. Symb. Comput., 84, 95-112 (2018) · Zbl 1429.13016
[51] Serre, J. P., Linear Representations of Finite Groups (1977), Springer-Verlag: Springer-Verlag New York-Heidelberg · Zbl 0355.20006
[52] Specht, W., Die irreduziblen Darstellungen der symmetrischen Gruppe, Math. Z., 39, 696-711 (1935) · JFM 61.0109.02
[53] Stanley, R., Invariants of finite groups and their applications to combinatorics, Bull. Am. Math. Soc. (N.S.), 1, 475-511 (1979) · Zbl 0497.20002
[54] Verschelde, J.; Gatermann, K., Symmetric Newton polytopes for solving sparse polynomial systems, Adv. Appl. Math., 16, 95-127 (1995) · Zbl 0832.65048
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.