PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Cubic Algorithm to Compute the Dynkin Type of a Positive Definite Quasi-Cartan Matrix

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Strony
369--384
Opis fizyczny
Bibliogr. 16 poz., rys., tab.
Twórcy
autor
  • Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico
autor
  • Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico
autor
  • Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico
Bibliografia
  • [1] Barot M, Geiss C, Zelevinsky A. Cluster algebras of finite type and positive symmetrizable matrices. Journal of the London Mathematical Society. 2006;73(3):545-564.
  • [2] Knapp AW. Lie Groups Beyond an Introduction. vol. 140 of Progress in Mathematics. 2nd ed. Birkhäuser; 2002. URL http://www.springer.com/book/978-0-8176-4259-4.
  • [3] Abarca M, Rivera D. Graph Theoretical and Algorithmic Characterizations of Positive Definite Symmetric Quasi-Cartan Matrices. Fundamenta Informaticae. 2016;149(3):241-261. doi:10.3233/FI-2016-1448.
  • [4] Barot M, Rivera D. Generalized Serre relations for Lie algebras associated with positive unit forms. Journal of Pure and Applied Algebra. 2007;211(2):360-373. URL https://doi.org/10.1016/j.jpaa.2007.01.008.
  • [5] Ovsienko SA. Integer weakly positive forms. Schurian Matrix problems and quadratic forms. 1978; pp. 3-17.
  • [6] Makuracki B, Simson D, Zyglarski B. Inflation Agorithm for Cox-regular Postive Edge-bipartite Graphs with Loops. Fundamenta Informaticae. 2017;153(4):367-398. doi:10.3233/FI-2017-1545.
  • [7] Barot M, De la Peña J. The Dynkin type of a non-negative unit form. Expositiones Mathematicae. 1999;17(4):339-348.
  • [8] Barot M. Introduction to the representation theory of algebras. Springer; 2012.
  • [9] Ringel CM. Tame Algebras and Integral Quadratic Forms. vol. 1099 of Lecture Notes in Mathematics. Springer-Verlag Berlin Heidelberg; 1984. doi:10.1007/BFb0072870.
  • [10] Bourbaki N. Groupes et algebres de Lie. vol. Ch. IV-VI of Paris. Hermann & Co.; 1960.
  • [11] Dlab V, Ringel C. Indecomposable representations of graphs and algebras. American Mathematical Society, 1976, 173, vol. 6(3). ISBN: 0-8218-1873-2.
  • [12] Kasjan S, Simson D. Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops, I. Mesh Root Systems. Fundamenta Informaticae. 2015;139:153-184. doi:10.3233/FI-2015-1230.
  • [13] Kasjan S, Simson D. Algorithms for Isotropy Groups of Cox-regular Edge-bipartite Graphs. Fundamenta Informaticae. 2015;139:249-275. doi:10.3233/FI-2015-1234.
  • [14] Kasjan S, Simson D. Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edgebipartite Graphs with Loops, II. Application to Coxeter Spectral Analysis. Fundamenta Informaticae. 2015;139:185-209. doi:10.3233/FI-2015-1231.
  • [15] Kosakowska J. Inflation Algorithms for Positive and Principal Edge-bipartite Graphs and Unit Quadratic Forms. Fundamenta Informaticae. 2012;119(2):149-162. URL http://content.iospress.com/articles/fundamenta-informaticae/fi119-2-02.
  • [16] Cormen TH. Introduction to algorithms. MIT press; 2009. ISBN: 10:0262033844, 13:978-0262033848.
Uwagi
Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-666bb1d9-7159-42cd-9e0c-4d450f710aff
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ć.