Inflations algorithm is a procedure that appears implicitly in Ovsienko’s classical proof for the classification of positive definite integral quadratic forms. The best known upper asymptotic bound for its time complexity is an exponential one. In this paper we show that this bound can be tightened to O(n6) for the naive implementation. Also, we propose a new approach to show how to decide whether an admissible quasi-Cartan matrix is positive definite and compute the Dynkin type in just O(n3) operations taking an integer matrix as input.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
A well known constructive proof for the ADE-classification of many mathematical objects, such as positive unit forms and their associated quasi-Cartan matrices, has lead to an Inflations Algorithm. However, this algorithm is not known to run in polynomial time. In this paper we use a so called flation transformation and show how its invariants can be used to characterize the Dynkin types A and D in the language of graph theory. Also, a polynomial-time algorithm for computing the Dynkin type is suggested.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.