NDLI: Computing Canonical Bases of Modules of Univariate Relations

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

Computing with Arithmetic Groups

Automated Geometric Reasoning with Geometric Algebra: Theory and Practice

On the Extended Hensel Construction and its Application to the Computation of Limit Points

Closed Form Solutions for Linear Differential and Difference Equations

Algorithmic Approaches for Lattice Path Combinatorics

An Algorithm for Computing Minimal Associated Primes of Binomial Ideals without Producing Redundant Components

The Zero Problem for Exponential Polynomials

Lattice Reduction Algorithms

Rational Points on the Unit Sphere: Approximation Complexity and Practical Constructions

Irreducibility and Deterministic r-th Root Finding over Finite Fields

A Case Study on the Parametric Occurrence of Multiple Steady States

Projection and Quantifier Elimination Using Non-uniform Cylindrical Algebraic Decomposition

The Complexity of an Adaptive Subdivision Method for Approximating Real Curves

Discriminants of Complete Intersection Space Curves

Fast Multiplication for Skew Polynomials

Big Prime Field FFT on the GPU

Criteria for Finite Difference Gröbner Bases of Normal Binomial Difference Ideals

Linear Time Fourier Transforms of $S_{n-k}-invariant$ Functions on the Symmetric Group $S_{n}$

Gcd Modulo a Primary Triangular Set of Dimension Zero

Calculating the Power Residue Symbol and Ibeta: Applications of Computing the Group Structure of the Principal Units of a p-adic Number Field Completion

Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits

Certificates for Triangular Equivalence and Rank Profiles

On Signature-Based Gröbner Bases Over Euclidean Rings

Matrix Representations by Means of Interpolation

Nemo/Hecke: Computer Algebra and Number Theory Packages for the Julia Programming Language

Parametrizations for Families of ECM-Friendly Curves

An Algebraic-Geometric Method for Computing Zolotarev Polynomials

Computing the Nearest Rank-Deficient Matrix Polynomial

Dimension-Dependent Upper Bounds for Gröbner Bases

A Constructive Approach to Arithmetics in Ore Localizations

Algorithms for Structured Linear Systems Solving and Their Implementation

Formula Simplification for Real Quantifier Elimination Using Geometric Invariance

Automated Generation of Non-Linear Loop Invariants Utilizing Hypergeometric Sequences

Efficiently Computing Real Roots of Sparse Polynomials

Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error Correction

Bounds for Substituting Algebraic Functions into D-finite Functions

Popov Form Computation for Matrices of Ore Polynomials

The Truncated Fourier Transform for Mixed Radices

Riemann Tensor Polynomial Canonicalization by Graph Algebra Extension

A New Algorithm for General Factorizations of Multivariate Polynomial Matrices

Algorithmic Verification of Linearizability for Ordinary Differential Equations

M4GB: An Efficient Gröbner-Basis Algorithm

Sparse Rational Univariate Representation

Resultants and Discriminants for Bivariate Tensor-Product Polynomials

Reconstruction Algorithms for Sums of Affine Powers

Denominator Bounds and Polynomial Solutions for Systems of q-Recurrences over K(t) for Constant K

Fast Algorithm for Border Bases of Artinian Gorenstein Algebras

Parametric Greatest Common Divisors using Comprehensive Gröbner Systems

Fast Computation of the Roots of Polynomials Over the Ring of Power Series

Computing Canonical Bases of Modules of Univariate Relations

Exploring the Dynamic Buchberger Algorithm

Growth in Varieties of Multioperator Algebras and Groebner Bases in Operads

Improved Bounds on Absolute Positiveness of Multivariate Polynomials

Characteristic Polynomials of p-adic Matrices

Two Fast Parallel GCD Algorithms of Many Integers

Factorization of Polynomials over $Z/(p^{n})$

CAD Adjacency Computation Using Validated Numerics

Functional Decomposition Using Principal Subfields

A Tropical F5 Algorithm

The Frobenius FFT

Composition Modulo Powers of Polynomials

Computing Canonical Bases of Modules of Univariate Relations

Content Provider	ACM Digital Library
Author	Neiger, Vincent Xuan, Vu Thi
Abstract	We study the computation of canonical bases of sets of univariate relations $(p_{1},.,p_{m})$ ∈ $K[x]^{m}$ such that $p_{1}$ $f_{1}$ + ⋯ + $p_{m}$ $f_{m}$ = 0; here, the input elements $f_{1},.,f_{m}$ are from a quotient $K[x]^{n}/M,$ where M is a K[x]-module of rank n given by a basis M ∈ K[x]n x n in Hermite form. We exploit the triangular shape of M to generalize a divide-and-conquer approach which originates from fast minimal approximant basis algorithms. Besides recent techniques for this approach, we rely on high-order lifting to perform fast modular products of polynomial matrices of the form P F mod M. Our algorithm uses $O~(m^{ω-1}D$ + $n^{ω}$ D/m) operations in K, where D = deg(det(M)) is the K-vector space dimension of $K[x]^{n}/M,$ O~(·) indicates that logarithmic factors are omitted, and ω is the exponent of matrix multiplication. This had previously only been achieved for a diagonal matrix M. Furthermore, our algorithm can be used to compute the shifted Popov form of a nonsingular matrix within the same cost bound, up to logarithmic factors, as the previously fastest known algorithm, which is randomized.
Starting Page	357
Ending Page	364
Page Count	8
File Format	PDF
ISBN	9781450350648
DOI	10.1145/3087604.3087656
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Division with remainder Polynomial matrix Shifted popov form Syzygy module Univariate equations
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