×

On the construction of general cubature formula by flat extensions. (English) Zbl 1386.65094

Summary: We describe a new method to compute general cubature formulae. The problem is initially transformed into the computation of truncated Hankel operators with flat extensions. We then analyze the algebraic properties associated to flat extensions and show how to recover the cubature points and weights from the truncated Hankel operator. We next present an algorithm to test the flat extension property and to additionally compute the decomposition. To generate cubature formulae with a minimal number of points, we propose a new relaxation hierarchy of convex optimization problems minimizing the nuclear norm of the Hankel operators. For a suitably high order of convex relaxation, the minimizer of the optimization problem corresponds to a cubature formula. Furthermore cubature formulae with a minimal number of points are associated to faces of the convex sets. We illustrate our method on some examples, and for each we obtain a new minimal cubature formula.

MSC:

65D32 Numerical quadrature and cubature formulas
15B05 Toeplitz, Cauchy, and related matrices
65D30 Numerical integration
90C22 Semidefinite programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Gillette, A. A.; Rand, A.; Bajaj, C., Error estimates for generalized barycentric coordinates, Adv. Comput. Math., 37, 3, 417-439 (2012) · Zbl 1259.65013
[2] Abrams, C.; Bussi, G., Enhanced sampling in molecular dynamics using metadynamics, replica-exchange and temperature acceleration, Entropy, 16, 163-199 (2014)
[3] Bajaj, C.; Bauer, B.; Bettadapura, R.; Vollrath, A., Non-uniform Fourier transforms for multi-dimensional rotational correlations, SIAM J. Sci. Comput., 35, 4, 821-845 (2013)
[4] Bayer, C.; Teichmann, J., The proof of Tchakaloff’s Theorem, Proc. Amer. Math. Soc., 134, 3035-3040 (2006) · Zbl 1093.41016
[5] Bernardi, A.; Brachat, J.; Comon, P.; Mourrain, B., General tensor decomposition, moment matrices and applications, J. Symbolic Comput., 52, 51-71 (2013) · Zbl 1275.15017
[6] Brachat, J.; Comon, P.; Mourrain, B.; Tsigaridas, E., Symmetric tensor decomposition, Linear Algebra Appl., 433, 1851-1872 (2010) · Zbl 1206.65141
[7] Patterson, T. N.L.; Morrow, C. R., Construction of algebraic cubature rules using polynomial ideal theory, SIAM J. Numer. Anal., 15, 953-976 (1978) · Zbl 0402.65013
[8] Caflisch, R.; Morokoff, W.; Owen, A., Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance, 1, 27-46 (1997)
[9] Cools, R., Constructing cubature formulae: the science behind the art, Acta Numer., 6, 1-54 (1997) · Zbl 0887.65028
[10] Cox, D., Solving equations via algebra, (Dickenstein, A.; Emiris, I. Z., Solving Polynomial Equations: Foundations, Algorithms, and Applications. Solving Polynomial Equations: Foundations, Algorithms, and Applications, Algorithms Comput. Math., vol. 14 (2005), Springer), 63-123 · Zbl 1152.13306
[11] Curto, R. E.; Fialkow, L. A., Recursiveness, positivity, and truncated moment problems, Houston J. Math., 17, 4, 603-635 (1991) · Zbl 0757.44006
[12] Curto, R. E.; Fialkow, L., Flat extensions of positive moment matrices: recursively generated relations, Mem. Amer. Math. Soc., 136, 648, 1-64 (1998) · Zbl 0913.47016
[13] Curto, R. E.; Fialkow, L., The truncated complex \(k\)-moment problem, Trans. Amer. Math. Soc., 352, 2825-2855 (2000) · Zbl 0955.47011
[14] Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry, Grad. Texts in Math., vol. 150 (1994), Springer-Verlag: Springer-Verlag Berlin
[15] Elkadi, M.; Mourrain, B., Introduction à la résolution des systèmes d’équations algébriques, Math. Appl., vol. 59 (2007), Springer-Verlag
[16] Fazel, M., Matrix rank minimization with applications (2002), Stanford University, PhD thesis
[17] Gillette, A.; Bajaj, C., Dual formulations of mixed finite element methods with applications, Comput. Aided Design, 43, 10, 1213-1221 (2011)
[18] Iohvidov, I. S., Hankel and Toeplitz Matrices and Forms: Algebraic Theory (1982), Birkhäuser: Birkhäuser Boston, MA, Translated from the Russian by G. Philip A. Thijsse. With an introduction by I. Gohberg · Zbl 0493.15018
[19] Lasserre, J. B., Moments, Positive Polynomials and Their Applications (2009), Imperial College Press
[20] Lasserre, J. B.; Laurent, M.; Mourrain, B.; Rostalski, P.; Trébuchet, P., Moment matrices, border bases and real radical computation, J. Symbolic Comput., 63-85 (2012) · Zbl 1276.13021
[21] Laurent, M., Revisiting two theorems of Curto and Fialkow on moment matrices, Proc. Amer. Math. Soc., 133, 2965-2976 (2005) · Zbl 1078.14085
[22] Laurent, M., Sums of Squares, Moment Matrices and Optimization over Polynomials, IMA Vol. Math. Appl., vol. 149, 157-270 (2009), Springer · Zbl 1163.13021
[23] Laurent, M.; Mourrain, B., A sparse flat extension theorem for moment matrices, Arch. Math., 93, 87-98 (2009) · Zbl 1183.30030
[24] Möller, H. M., Kubaturformeln mit minimaler knotenzahl, Numer. Math., 25, 2, 185-200 (1975/1976) · Zbl 0319.65019
[25] Möller, H. M., Lower bounds for the number of nodes in cubature formulae, (Hämmerlin, G., Numerische Integration. Numerische Integration, International Series of Numerical Mathematics/Internationale Schriftenreihe zur Numerischen Mathematik/Série Internationale D’Analyse Numérique, vol. 45 (1979), Birkhäuser: Birkhäuser Basel), 221-230 · Zbl 0416.65019
[26] Möller, H. M., Lower bounds for the number of nodes in cubature formulae, (Numerische Integration. Numerische Integration, Internat. Ser. Numer. Math., vol. 45 (1979)), 221-230 · Zbl 0416.65019
[27] Mourrain, B., A new criterion for normal form algorithms, (AAECC (1999)), 430-443 · Zbl 0976.12005
[28] Mourrain, B.; Trébuchet, P., Generalized normal forms and polynomials system solving, (Kauers, M., ISSAC: Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation (2005)), 253-260 · Zbl 1360.68947
[29] Mysovskikh, I. P., A proof of minimality of the number of nodes of a cubature formula for a hypersphere, Z. Vycisl. Mat. i Mat. Fiz., 6, 621-630 (1966), (in Russian) · Zbl 0154.17903
[30] Mysovskikh, I. P., Interpolational Cubature Formulas, 1-336 (1981), Nauka: Nauka Moscow, (in Russian) · Zbl 0537.65019
[31] Nesterov, Y.; Nemirovski, A., Interior-Point Polynomial Algorithms in Convex Programming (1994), SIAM: SIAM Philadelphia · Zbl 0824.90112
[32] Ninomiya, S.; Tezuka, S., Toward real time pricing of complex financial derivatives, Appl. Math. Finance, 3, 1-20 (1996) · Zbl 1097.91530
[33] Putinar, M., A dilation theory approach to cubature formulas, Expo. Math., 15, 183-192 (1997) · Zbl 0888.47004
[34] Radon, J., Zur mechanischen kubatur, Monatsh. Math., 52, 286-300 (1948), (in German) · Zbl 0031.31504
[35] Rand, A.; Gillette, A.; Bajaj, C., Interpolation error estimates for mean value coordinates, Adv. Comput. Math., 39, 327-347 (2013) · Zbl 1275.41005
[36] Rand, A.; Gillette, A.; Bajaj, C., Quadratic serendipity finite elements on polygons using generalized barycentric coordinates, Math. Comp., 83, 2691-2716 (2014) · Zbl 1300.65091
[37] Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[38] Schmid, H. J., Two-dimensional minimal cubature formulas and matrix equations, SIAM J. Matrix Anal. Appl., 16, 898-921 (1995) · Zbl 0832.65017
[39] Schmid, H. J.; Xu, Y., On bivariate Gaussian cubature formulae, Proc. Amer. Math. Soc., 122, 833-841 (1994) · Zbl 0812.65013
[40] Stroud, A. H., Quadrature methods for functions of more than one variable, Ann. N.Y. Acad. Sci., 86, 776-791 (1960) · Zbl 0102.33703
[41] Stroud, A. H., Integration formulas and orthogonal polynomials, SIAM J. Numer. Anal., 7, 271-276 (1970) · Zbl 0215.27302
[42] Tchakaloff, V., Formules de cubatures mécaniques à coefficients non négatifs, Bull. Sci. Math. (2), 81, 123-134 (1957) · Zbl 0079.13908
[43] Wachpress, E., A Rational Finite Element Basis (1975), Academic Press
[44] Xu, Y., Common zeros of polynomials in several variables and higher-dimensional quadrature, Pitman Res. Notes Math. Ser., 312, 312, 119 (1994) · Zbl 0898.26004
[45] Xu, Y., Cubature formulae and polynomial ideals, Adv. in Appl. Math., 23, 211-233 (1999) · Zbl 0954.65020
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.