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(rm6n2(n + mlog 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 O(rm4n2(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).
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ć.