Integration of polynomials over n-dimensional simplices

• Autorzy: Rouigueb Abdenebi , Maiza Mohamed , Tkourt Abderahmane , Cherchour Imed

Identyfikatory

DOI

10.15439/2019F16

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

Integrating an arbitrary polynomial function f of degree D over a general simplex in dimension n is well-known in the state of the art to be NP-hard when D and n are allowed to vary, but it is time-polynomial when D or n are fixed. This paper presents an efficient algorithm to compute the exact value of this integral. The proposed algorithm has a time-polynomial complexity when D or n are fixed, and it requires a reasonable time when the values of D and n are less than 10 using widely available standard calculators such as desktops.

Słowa kluczowe

EN

computational complexity; polynomials; NP-hard

PL

złożoność obliczeniowa; wielomian; problem NP-trudny

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 18
• Strony: 157--163
• Opis fizyczny: Bibliogr. 8 poz., wz., wykr., tab.

Twórcy

autor

Rouigueb Abdenebi

• Ecole Militaire Polytechnique Data Fusion and Analysis Laboratory, Algiers, Algeria

autor

Maiza Mohamed

• Ecole Militaire Polytechnique Modeling and Optimization Techniques Laboratory, Algiers, Algeria

autor

Tkourt Abderahmane

• Ecole Militaire Polytechnique Modeling and Optimization Techniques Laboratory, Algiers, Algeria

autor

Cherchour Imed

• Ecole Militaire Polytechnique Data Fusion and Analysis Laboratory, Algiers, Algeria

Bibliografia

• 1. V. Baldoni and N. Berline and J. A. De Loera and M. Köppe and M. Vergne, “How to Integrate a Polynomial over a Simplex,” Math. Comput. J., vol. 80, 2011, pp. 297–325.
• 2. M. E. Dyer and A. M. Frieze, “Frieze, On the complexity of computing the volume of a polyhedron,” SIAM J. Comput. vol. 17, no. 5, 1961, pp. 967-974.
• 3. J. A. De Loera, J. Rambau, and F. Santos, Triangulations: Structures and algorithms, Book manuscript, 2008.
• 4. A. H. Stroud, Approximate Calculation of Multiple Integrals. Prentice-Hall, Englewood Cliffs, NJ, 1971.
• 5. A. Grundmann and H. M. Moller, “Invariant Integration Formulas for the n-Simplex by Combinatorial Methods,” SIAM J. Numer. Anal. vol. 17, no. 5, 1961, pp. 282-290.
• 6. P. C. Hammer and A. H. Stroud, “Numerical integration over simplexes,” Math Tables other Aids Comput. vol. 10, 1956, pp. 137-139.
• 7. F. Bernardini, “Integration of polynomials over n-dimensional polyhedra,” Computer-Aided Design vol. 23, no. 11, 1991, pp. 51-58.
• 8. A. H. Stroud, Approximate Calculation of Multiple Integrals, PrenticeHall, Englewood Cliffs, NJ, 1971. a product of linear forms

Uwagi

1. Track 1: Artificial Intelligence and Applications

2. Technical Session: 12th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).