NDLI: Fast computation of Smith forms of sparse matrices over local rings

Please wait, while we are loading the content...

A-hypergeometric functions: computational aspects

Complexity of deciding connectivity in real algebraic sets: recent results and future research directions

Asymptotic spectrum and matrix multiplication

Upper bounds on real roots and lower bounds for the permanent

Elements of computer-algebraic analysis

Algebraic statistics

On valuations of meromorphic solutions of arbitrary-order linear difference systems with polynomial coefficients

Computing Puiseux series for algebraic surfaces

The M4RIE library for dense linear algebra over small fields with even characteristic

A root isolation algorithm for sparse univariate polynomials

Computing closed form solutions of integrable connections

Solving linear ordinary differential systems in hyperexponential extensions

Relaxed p-adic Hensel lifting for algebraic systems

Solving polynomial systems over finite fields: improved analysis of the hybrid approach

A polynomial time algorithm for computing the HNF of a module over the integers of a number field

Parallel sparse polynomial multiplication on modern hardware architectures

Compositions and collisions at degree $p^{2}$

Fast computation of common left multiples of linear ordinary differential operators

Power series solutions of singular (q)-differential equations

On the complexity of solving initial value problems

Order-degree curves for hypergeometric creative telescoping

Telescopers for rational and algebraic functions via residues

Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values

Fast computation of Smith forms of sparse matrices over local rings

On the complexity of solving a bivariate polynomial system

Critical points and Gröbner bases: the unmixed case

Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of N vortices in the plane

Twisting q-holonomic sequences by complex roots of unity

Improving the accuracy of linear programming solvers with iterative refinement

Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions

Practical Gröbner basis computation

On the complexity of multivariate blockwise polynomial multiplication

Rational invariants of scalings from Hermite normal forms

Zeilberger's holonomic ansatz for Pfaffians

Algorithms for the universal decomposition algebra

An efficient implementation of the algorithm computing the Borel-fixed points of a Hilbert scheme

Computing real solutions of polynomial systems via low-rank moment matrix completion

Small homogeneous quandles

Border basis representation of a general quotient algebra

An algorithm to compute the differential equations for the logarithm of a polynomial

Deterministic unimodularity certification

Programming before theorizing, a case study

When Newton meets Descartes: a simple and fast algorithm to isolate the real roots of a polynomial

Effective de Rham cohomology: the hypersurface case

Construction of 2-closed M-representations

Near optimal tree size bounds on a simple real root isolation algorithm

An efficient programming model for memory-intensive recursive algorithms using parallel disks

Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas

Univariate real root isolation in multiple extension fields

A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras

Factorization of differential operators with ordinary differential polynomial coefficients

Computing minimal nullspace bases

Fast computation of Smith forms of sparse matrices over local rings

Content Provider	ACM Digital Library
Author	Giesbrecht, Mark Novocin, Andy Saunders, B. David Elsheikh, Mustafa
Abstract	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 x n matrix A over the ring $F[z]/(f^{e}),$ where $f^{e}$ is a power of an irreducible polynomial f ∈ F[z] of degree d, our algorithm requires $O(ηde^{2}n)$ operations in F, where our black-box is assumed to require O(η) operations in F to compute a matrix-vector product by a vector over $F[z]/(f^{e})$ (and η is assumed greater than nde). The algorithm only requires additional storage for O(nde) elements of F. In particular, if η = O(nde), then our algorithm requires only $O(n^{2}d^{2}e^{3})$ operations in F, which is an improvement on known dense methods for small d and e. For the ring $Z/p^{e}Z,$ 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 μnre log p, where μ is the number of operations in Z/pZ 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.
Starting Page	146
Ending Page	153
Page Count	8
File Format	PDF
ISBN	9781450312691
DOI	10.1145/2442829.2442853
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Polynomial matrix Local principal ideal ring Sparse matrix Black box Smith form Complexity Integer matrix
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in