On the Computational Complexity of Bongartz's Algorithm

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 𝒪(rm⁶n²(n + m log 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 𝒪(rm⁴n²(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).