Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: isomorphism problem

Sortuj według:

Ogranicz wyniki do:

On the Computational Complexity of Bongartz’s Algorithm

Mróz A.

Fundamenta Informaticae

2013

Vol. 123, nr 3

317--329

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).