Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleJuly 2014
Algebraic complexity theory and matrix multiplication
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPage 23https://doi.org/10.1145/2608628.2627493This tutorial will give an overview of algebraic complexity theory focused on bilinear complexity, and describe several powerful techniques to analyze the complexity of computational problems from linear algebra, in particular matrix multiplication. The ...
- research-articleJuly 2014
Maximum likelihood for matrices with rank constraints
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPage 17https://doi.org/10.1145/2608628.2627490Maximum likelihood estimation is a fundamental computational task in statistics. We address this problem for manifolds of low rank matrices. These represent mixtures of independent distributions of two discrete random variables. This non-convex ...
- research-articleJuly 2014
Fuzzy simplification of non-numeric expressions containing some intervals and/or floating point numbers
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 9–16https://doi.org/10.1145/2608628.2627489This article describes a Mathematica package that improves simplification of general non-numeric expressions containing any mixture of Gaussian rational numbers, symbolic constants, machine and arbitrary-precision floating-point numbers, together with ...
- research-articleJuly 2014
Linear independence oracles and applications to rectangular and low rank linear systems
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 381–388https://doi.org/10.1145/2608628.2608673Randomized algorithms are given for linear algebra problems on an input matrix A ∈ Knxm over a field K. We give an algorithm that simultaneously computes the row and column rank profiles of A in 2r3 + (r2 + n + m + |A|)1+o(1) field operations from K, ...
- research-articleJuly 2014
Fast arithmetic for the algebraic closure of finite fields
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 122–129https://doi.org/10.1145/2608628.2608672We present algorithms to construct and do arithmetic operations in the algebraic closure of the finite field Fp. Our approach is inspired by algorithms for constructing irreducible polynomials, which first reduce to prime power degrees, then use ...
- research-articleJuly 2014
Powers of tensors and fast matrix multiplication
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 296–303https://doi.org/10.1145/2608628.2608664This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic construction also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches,...
- research-articleJuly 2014
Sparse polynomial interpolation codes and their decoding beyond half the minimum distance
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 272–279https://doi.org/10.1145/2608628.2608660We present algorithms performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Based on the initial work by Comer, Kaltofen and Pernet [Proc. ISSAC 2012], we define the sparse polynomial interpolation codes ...
- research-articleJuly 2014
Synthesis of optimal numerical algorithms using real quantifier elimination (case study: square root computation)
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 162–169https://doi.org/10.1145/2608628.2608654We report on on-going efforts to apply real quantifier elimination to the synthesis of optimal numerical algorithms. In particular, we describe a case study on the square root problem: given a real number x and an error bound ε, find a real interval ...
- research-articleJuly 2014
Tame decompositions and collisions
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 421–428https://doi.org/10.1145/2608628.2608653A univariate polynomial f over a field is decomposable if f = g o h = g(h) for nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field. The tame case, where ...
- research-articleJuly 2014
A new deterministic algorithm for sparse multivariate polynomial interpolation
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 51–58https://doi.org/10.1145/2608628.2608648We present a deterministic algorithm to interpolate an m-sparse n-variate polynomial which uses poly(n, m, log H, log d) bit operations. Our algorithm works over the integers. Here H is a bound on the magnitude of the coefficient values of the given ...
- research-articleJuly 2014
Online order basis algorithm and its impact on the block Wiedemann algorithm
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 202–209https://doi.org/10.1145/2608628.2608647Order bases are a fundamental tool for linear algebra with polynomial coefficients. In particular, block Wiedemann methods are nowadays able to tackle large sparse matrix problems because they benefit from fast order basis algorithms. However, such fast ...
- research-articleJuly 2014
LLL reducing with the most significant bits
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 367–374https://doi.org/10.1145/2608628.2608645Let B be a basis of a Euclidean lattice, and B an approximation thereof. We give a sufficient condition on the closeness between B and B so that an LLL-reducing transformation U for B remains valid for B. Further, we analyse an efficient reduction ...
- research-articleJuly 2014
The MMO problem
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 186–193https://doi.org/10.1145/2608628.2608643We consider a two polynomials analogue of the polynomial interpolation problem. Namely, we consider the Mixing Modular Operations (MMO) problem of recovering two polynomials f ∈ Zp[x] and g ∈ Zq[x] of known degree, where p and q are two (un)known ...
- research-articleJuly 2014
Sparse multivariate function recovery with a high error rate in the evaluations
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 280–287https://doi.org/10.1145/2608628.2608637In [Kaltofen and Yang, Proc. ISSAC 2013] we have generalized algebraic error-correcting decoding to multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe ...
- research-articleJuly 2014
Evaluating parametric holonomic sequences using rectangular splitting
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 256–263https://doi.org/10.1145/2608628.2608629We adapt the rectangular splitting technique of Paterson and Stockmeyer to the problem of evaluating terms in holonomic sequences that depend on a parameter. This approach allows computing the n-th term in a recurrent sequence of suitable type using O(n...
- proceedingJuly 2014
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation
The 2014 International Symposium on Symbolic and Algebraic Computation (ISSAC) is the premier conference for research in symbolic computation and computer algebra. ISSAC 2014, held at Kobe University, Japan, is the 39th meeting in the series, which ...