On the Computational Complexity of Bongartz’s Algorithm

• Autorzy: Mróz A.
• Języki publikacji: EN

Abstrakty

EN

We study the complexity of Bongartz’s algorithm for determining a maximal common direct summand of a pair of modules M,N over k-algebra ; in particular, we estimate its pessimistic computational complexity O(rm⁶n²(n + mlog n)), where m = dim_kM ≤ n = dim_kN and r is a number of common indecomposable direct summands of M and N. We improve the algorithm to another one of complexity O(rm⁴n²(n+mlogm)) and we show that it applies to the isomorphism problem (having at least an exponential complexity in a direct approach). Moreover, we discuss a performance of both algorithms in practice and show that the “average” complexity is much lower, especially for the improved one (which becomes a part of QPA package for GAP computer algebra system).

Słowa kluczowe

EN

algorithm; computational complexity; computer algebra; GAP; module; common direct summand; Gaussian elimination; decomposition; isomorphism problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 3
• Strony: 317--329
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Mróz A.

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland

Bibliografia

• [1] I. Assem, D. Simson and A. Skowroński, Elements of the Representation Theory of Associative Algebras, Vol. 1, Techniques of Representation Theory, London Math. Soc. Student Texts 65, Cambridge Univ. Press, Cambridge - New York, 2006.
• [2] G. Belitskii and V. V. Sergeichuk, Complexity of matrix problems, Linear Algebra Appl. 361 (2003), 203–222.
• [3] K. Bongartz, Gauß-Elimination und der größte gemeinsame direkte Summand von zwei endlichdimensionalen Moduln, Arch. Math. Vol 53 (1989), 256-258.
• [4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT, 1990.
• [5] C.W. Curtis and I. Reiner, Methods of representation theory, Vol. 1, New York-London-Sidney, 1981.
• [6] P. Dowbor and A. Mr´oz, The multiplicity problem for indecomposable decompositions of modules over a finite-dimensional algebra. Algorithms and a computer algebra approach, Colloq. Math. 107 (2007), 221-261.
• [7] P. Dowbor and A. Mr´oz, The multiplicity problem for indecomposable decompositions of modules over domestic canonical algebras, Colloq. Math. 111 (2008), 221-282.
• [8] P. Dowbor and A. Mróz, On a separation of orbits in the module variety for domestic canonical algebras, Colloq. Math. 111 (2008), 283-295.
• [9] P. Dowbor and A. Mróz, On a separation of orbits in the module variety for string special biserial algebras, J. Pure Appl. Algebra 213 (2009) 1804-1815.
• [10] M. Grzecza, S. Kasjan and A. Mróz, Tree matrices and a matrix reduction algorithm of Belitskii, Fund. Inform. 118 (2012), 253-279.
• [11] S. Kasjan and A. Mróz, Experiences in symbolic computations for matrix problems, 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2012, in press.
• [12] K. Kawarabayashi and B. Mohar, Star coloring and acyclic coloring of locally planar graphs, SIAM J. Discrete Math. 24 (2010), 56–71.
• [13] D. Ke¸dzierski and H. Meltzer, Indecomposable representations of extended Dynkin quivers of type e E8, Colloq. Math. 124 (2011), no. 1, 95-116.
• [14] A. Kisielewicz and M. Szykuła, Rainbow induced subgraphs in proper vertex colorings, Fund. Inform. 111 (2011), 437–451.
• [15] J. Kosakowska, Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform., 119 (2012), 149-162.
• [16] J. Kosakowska and D. Simson, Hereditary coalgebras and representations of species, J. Algebra 293 (2005), 457–505.
• [17] A. Mróz, On the multiplicity problem and the isomorphism problem for the four subspace algebra, Comm. Algebra 40:6 (2012), 2005-2036.
• [18] C. M. Ringel and M. Schmidmeier, Invariant subspaces of nilpotent linear operators, I, J. reine angew. Math. 614 (2008), 1-52.
• [19] V. V. Sergeichuk, Canonical matrices for linear matrix problems, Linear Algebra Appl. 317 (2000), 53–102.
• [20] D. Simson, Prinjective modules, propartite modules, representations of bocses and lattices over orders, J. Math. Soc. Japan, 49 (1997), 31–68.
• [21] D. Simson, Representation types of the category of subprojective representations of a finite poset over K[t]/(tm) and a solution of a Birkhoff type problem, J. Algebra 311 (2007), 1-30.
• [22] D. Simson, Mesh algorithms for solving principal diophantine equations, sand-glass tubes and tori of roots, Fund. Inform. 109 (2011), 425–462, doi: 10.3233//FI-2011-603.
• [23] D. Simson, Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform. 119 (2012), in press.
• [24] D. Simson, A Coxeter-Gram classification of simply-laced edge-bipartite graphs, SIAM J. Discr. Math. 2012, to appear.
• [25] D. Simson and A. Skowro´nski, Elements of the Representation Theory of Associative Algebras, Vol. 3. Representation-Infinite Tilted Algebras, London Math. Soc. Student Texts 72, Cambridge Univ. Press, Cambridge-New York, 2007.
• [26] D. Simson and M. Wojewódzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83 (2008), 389–410.
• [27] GAP, http://www.gap-system.org.
• [28] QPA, http://quiverspathalg.sourceforge.net.