BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
For a prime p and a matrix A∈Zn×n, write A as A=p(Aquop)+(Aremp) where the remainder and quotient operations are applied element-wise. Write the p-adic expansion of A as A=A[0]+pA[1]+p2A[2]+⋯ where each A[i]∈Zn×n has entries between [0,p−1]. Upper bounds are proven for the Z-ranks of Aremp, and Aquop. Also, upper bounds are proven for the Z/pZ-rank of A[i] for all i≥0 when p=2, and a conjecture is presented for odd primes.
We present algorithms to compute the Smith Normal Form of matrices over two families of local rings. The algorithms use the \emph{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 $\nxn$ matrix A over the ring $\Fzfe$, where fe is a power of an irreducible polynomial $f \in \Fz$ of degree d, our algorithm requires $\bigO(ηde^2n)$ operations in $\F$, where our black-box is assumed to require $\bigO(η)$ operations in $\F$ to compute a matrix-vector product by a vector over $\Fzfe$ (and η is assumed greater than $\Pden$). The algorithm only requires additional storage for $\bigO(\Pden)$ elements of $\F$. In particular, if $η=\softO(\Pden)$, then our algorithm requires only $\softO(n^2d^2e^3)$ operations in $\F$, which is an improvement on known dense methods for small d and e. For the ring $\ZZ/p^e\ZZ$, 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 time complexity is essentially linear in μnrelogp, where μ is the number of operations in $\ZZ/p\ZZ$ to evaluate the black-box (assumed greater than n) and r is the total number of non-zero invariant factors. 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 restrictions on the number of nontrivial invariant factors remains open. We offer a conjecture which may contribute toward that end.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.