Optimal Parenthesizing of Geometric Algebra Products
| Autor: | Stéphane Breuils, Vincent Nozick, Akihiro Sugimoto |
|---|---|
| Přispěvatelé: | National Institute of Informatics (NII), Université Gustave Eiffel, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Quadric
Order (ring theory) Outer product Conformal map 0102 computer and information sciences 01 natural sciences Expression (mathematics) Dynamic programming Algebra Geometric algebra 010201 computation theory & mathematics 0103 physical sciences 010307 mathematical physics Associative property Mathematics [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS] |
| Zdroj: | Computer Graphics International Conference Computer Graphics International Conference, Oct 2020, Geneva, Switzerland. pp.492-500 CGI 2020 CGI 2020, Oct 2020, Geneva, Switzerland. pp.492-500, ⟨10.1007/978-3-030-61864-3_42⟩ Advances in Computer Graphics ISBN: 9783030618636 CGI |
| DOI: | 10.1007/978-3-030-61864-3_42⟩ |
| Popis: | International audience; Manipulating objects using geometric algebra may involve several associative products in a single expression. For example, an object can be constructed by the outer product of multiple points. This number of products can be small for some conformal algebra and high for higher dimensional algebras such as quadric conformal geometric algebras. In these situations, the order of products (i.e. the choice of the parenthesis in the expression) should not change the final result but may change the overall computational cost, according to the grade of the intermediate multivectors. Indeed, the usual left to right way to evaluate the expression may not be most computationally efficient. Studies on the number of arithmetic operations of geometric algebra expressions have been limited to products of only two homogeneous multivectors. This paper shows that there exists an optimal order in the evaluation of an expression involving geometric and outer products, and presents a dynamic programming framework to find it. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|