Fast Computation of Smith Forms of Sparse Matrices Over Local Rings

Details Fast Computation of Smith Forms of Sparse Matrices Over Local Rings Fast Computation of Smith Forms of Sparse Matrices Over Local Rings

2012-01-25

arxiv.org/abs/1201.5365v1

Computer Science

Symbolic Computation

Scientific paper

We present algorithms to compute the Smith normal form of matrices over two families of local rings. The algorithms use the black box model which is suitable for sparse and structured matrices. The algorithms depend on a number of tools, such as matrix rank computation over finite fields, for which the best-known time- and memory-efficient algorithms are probabilistic. For an n by n matrix A over the ring F[z]/(f^e), where f^e is a power of an irreducible polynomial f in F[z] of degree d, our algorithm requires O({\mu}*de^2n) operations in F, where our black box is assumed to require O({\mu}) operations in F to compute a matrix-vector product by a vector over F[z]/(f^e) (and {\mu} is assumed greater than den. The algorithm only requires additional storage for O(den) elements of F. In particular, if {\mu}=O(den), then our algorithm requires only O^{\sim}(n^2d^2e^3) operations in F, which is an improvement on previous methods for small d and e. For the ring Z/p^eZ, where p is a prime, we give an algorithm which is time- and memory-efficient when the number of nontrivial invariant factors is small. We describe a method for dimension reduction while preserving the invariant factors. The runtime is essentially linear in ne{\mu} log(p), where {\mu} is the cost of black-box evaluation (assumed greater than n). To avoid the practical cost of conditioning, we give a Monte Carlo certificate, which at low cost, provides either a high probability of success or a proof of failure. The quest for a time and memory efficient solution without the restriction on number of nontrivial invariant factors remains open. We offer a conjecture which may contribute toward that end.

Affiliated with

Also associated with

No associations

Rating

Fast Computation of Smith Forms of Sparse Matrices Over Local Rings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Computation of Smith Forms of Sparse Matrices Over Local Rings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Computation of Smith Forms of Sparse Matrices Over Local Rings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444303