A New Algorithm for Computing the Smith Normal Form and its Implementation on Parallel Machines
2004 (English)In: Proceedings of 6th Workshop on Advances in Parallel and Distributed Computation Models, International Parallel and Distributed Processing Symposium (IPDPS 2004), IEEE Press, 2004Conference paper (Refereed)
Smith normal form computation is important in many topics, e.g. group theory and number theory. For matrices over the rings Z and F2 [x], we introduce a new Smith normal form algorithm, called Triangular Band Matrix Algorithm, which first computes the Hermite Normalform and then step by step the diagonal form and the Smith normal form. In comparison to the Kannan Bachem Algorithm, which computes the Smith normal form by alternately computing the Hermite normal form and the left Hermite normal form, the theoretical advantage is, that we only once apply the expensive Hermite normal form step. We parallelize the Triangular Band Matrix Algorithm and get a better complexity analysis than for previous parallel algorithms, like the Kannan Bachem Algorithm and the Hartley Hawkes Algorithm. In the part, which is different to the Kannan Bachem Algorithm, the Triangular Band Matrix Algorithm leads to a better efficiency and smaller execution times, even for large example matrices.
Place, publisher, year, edition, pages
IEEE Press, 2004.
IdentifiersURN: urn:nbn:se:umu:diva-84346OAI: oai:DiVA.org:umu-84346DiVA: diva2:683139
6th Workshop on Advances in Parallel and Distributed Computation Models, International Parallel and Distributed Processing Symposium (IPDPS 2004)