On the Computational Complexity of Bongartz's Algorithm

Article type: Research Article

Authors: Mróz, Andrzej

Affiliations: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland. amroz@mat.umk.pl

Note: [] Address for correspndence: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland

Abstract: 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 𝒪(rm6n2(n + m log n)), where m = dimkM ≤ n = dimkN and r is a number of common indecomposable direct summands of M and N. We improve the algorithm to another one of complexity 𝒪(rm4n2(n+m log m)) 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).

Keywords: algorithm, computational complexity, computer algebra, GAP, module, common direct summand, Gaussian elimination, decomposition, isomorphism problem

DOI: 10.3233/FI-2013-813

Journal: Fundamenta Informaticae, vol. 123, no. 3, pp. 317-329, 2013