[go: up one dir, main page]

Van Der Hoeven et al., 2013 - Google Patents

On the bit-complexity of sparse polynomial and series multiplication

Van Der Hoeven et al., 2013

View PDF
Document ID
14275515281705041096
Author
Van Der Hoeven J
Lecerf G
Publication year
Publication venue
Journal of Symbolic Computation

External Links

Snippet

In this paper we present various algorithms for multiplying multivariate polynomials and series. All algorithms have been implemented in the C++ libraries of the Mathemagix system. We describe naive and softly optimal variants for various types of coefficients and …
Continue reading at www.sciencedirect.com (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/726—Inversion; Reciprocal calculation; Division of elements of a finite field
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/141—Discrete Fourier transforms
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/725—Finite field arithmetic over elliptic curves
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F19/00—Digital computing or data processing equipment or methods, specially adapted for specific applications
    • G06F19/70—Chemoinformatics, i.e. data processing methods or systems for the retrieval, analysis, visualisation, or storage of physicochemical or structural data of chemical compounds
    • G06F19/708—Chemoinformatics, i.e. data processing methods or systems for the retrieval, analysis, visualisation, or storage of physicochemical or structural data of chemical compounds for data visualisation, e.g. molecular structure representations, graphics generation, display of maps or networks or other visual representations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7209—Calculation via subfield, i.e. the subfield being GF(q) with q a prime power, e.g. GF ((2**m)**n) via GF(2**m)

Similar Documents

Publication Publication Date Title
Van Der Hoeven et al. On the bit-complexity of sparse polynomial and series multiplication
Abreu et al. Differential equations from unitarity cuts: nonplanar hexa-box integrals
Lenstra Algorithms in algebraic number theory
Ivanyos et al. Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem
Enge et al. A general framework for subexponential discrete logarithm algorithms
Bernstein Fast multiplication and its applications
Hoyer Efficient quantum transforms
Ni et al. A non-commuting stabilizer formalism
Azar et al. Approximating probability distributions using small sample spaces
Püschel et al. Fast quantum Fourier transforms for a class of non-abelian groups
Nakos Nearly optimal sparse polynomial multiplication
Eberly Very fast parallel polynomial arithmetic
Bhargava et al. Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
Van Peski Hall–Littlewood polynomials, boundaries, and p-adic random matrices
Cano et al. Formalized linear algebra over elementary divisor rings in Coq
Beukers et al. Lamé equations with algebraic solutions
Feliu-Fabà et al. Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
Khanna et al. Code sparsification and its applications
Arnold Sparse polynomial interpolation and testing
De Feo Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic
Bostan et al. Low complexity algorithms for linear recurrences
Chen et al. Multiplying boolean polynomials with Frobenius partitions in additive fast Fourier transform
Macdonald et al. Logspace and compressed-word computations in nilpotent groups
Bernstein Optimizing linear maps modulo 2
Xiao et al. Supersingular j-invariants and the class number of ℚ (− p)