### Top 10 Arxiv Papers Today in Symbolic Computation

##### #1. Algebraic number fields and the LLL algorithm
###### M. J. Uray
In this paper we analyze the computational cost of various operations performed symbolically in real algebraic number fields where the elements are represented as polynomials of a primitive element of the field. We give bounds on the costs in terms of several parameters, including the degree of the field and the representation size of the input. Beyond the basic field operations we also analyze the cost of the less-than comparison and the integer rounding functions. As an important application we give a polynomial bound on the running time of the LLL lattice reduction algorithm when the vector coordinates are from an algebraic number field and the computations are performed exactly.
more | pdf | html
None.
###### Tweets
ComputerPapers: Algebraic number fields and the LLL algorithm. https://t.co/rglJqIMNaK
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8961
Unqiue Words: 2005

##### #2. Proceedings of the 15th International Workshop on the ACL2 Theorem Prover and Its Applications
###### Shilpi Goel, Matt Kaufmann
This volume contains the proceedings of the Fifteenth International Workshop on the ACL2 Theorem Prover and Its Applications (ACL2-2018), a two-day workshop held in Austin, Texas, USA, on November 5-6, 2018, immediately after FMCAD'18. The proceedings of ACL2-2018 include eleven long papers and two extended abstracts.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #3. Fast transforms over finite fields of characteristic two
###### Nicholas Coxon
An additive fast Fourier transform over a finite field of characteristic two efficiently evaluates polynomials at every element of an $\mathbb{F}_2$-linear subspace of the field. We view these transforms as performing a change of basis from the monomial basis to the associated Lagrange basis, and consider the problem of performing the various conversions between these two bases, the associated Newton basis, and the '' novel '' basis of Lin, Chung and Han (FOCS 2014). Existing algorithms are divided between two families, those designed for arbitrary subspaces and more efficient algorithms designed for specially constructed subspaces of fields with degree equal to a power of two. We generalise techniques from both families to provide new conversion algorithms that may be applied to arbitrary subspaces, but which benefit equally from the specially constructed subspaces. We then construct subspaces of fields with smooth degree for which our algorithms provide better performance than existing algorithms.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 27382
Unqiue Words: 2924

##### #4. Linear Differential Equations as a Data-Structure
###### Bruno Salvy
A lot of information concerning solutions of linear differential equations can be computed directly from the equation. It is therefore natural to consider these equations as a data-structure, from which mathematical properties can be computed. A variety of algorithms has thus been designed in recent years that do not aim at "solving", but at computing with this representation. Many of these results are surveyed here.
more | pdf | html
###### Tweets
jjcarett2: "Linear Differential Equations as a Data-Structure" by B. Salvy - https://t.co/Sn6y3qpuxp is something that @sigfpe should be quite interested in. @ccshan and I definitely use some of these ideas in Hakaru.
ComputerPapers: Linear Differential Equations as a Data-Structure. https://t.co/oRNFPUcvoQ
darkproger: RT @jjcarett2: "Linear Differential Equations as a Data-Structure" by B. Salvy - https://t.co/Sn6y3qpuxp is something that @sigfpe should…
paul_snively: RT @jjcarett2: "Linear Differential Equations as a Data-Structure" by B. Salvy - https://t.co/Sn6y3qpuxp is something that @sigfpe should…
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 18067
Unqiue Words: 4538

##### #5. Chordal Graphs in Triangular Decomposition in Top-Down Style
###### Chenqi Mou, Yang Bai, Jiahua Lai
In this paper, we first prove that when the associated graph of a polynomial set is chordal, a particular triangular set computed by a general algorithm in top-down style for computing the triangular decomposition of this polynomial set has an associated graph as a subgraph of this chordal graph. Then for Wang's method and a subresultant-based algorithm for triangular decomposition in top-down style and for a subresultant-based algorithm for regular decomposition in top-down style, we prove that all the polynomial sets appearing in the process of triangular decomposition with any of these algorithms have associated graphs as subgraphs of this chordal graph. These theoretical results can be viewed as non-trivial polynomial generalization of existing ones for sparse Gaussian elimination, inspired by which we further propose an algorithm for sparse triangular decomposition in top-down style by making use of the chordal structure of the polynomial set. The effectiveness of the proposed algorithm for triangular decomposition, when the...
more | pdf | html
###### Tweets
ComputerPapers: Chordal Graphs in Triangular Decomposition in Top-Down Style. https://t.co/FaXtZFALpO
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 13699
Unqiue Words: 2421

##### #6. What Can (and Can't) we Do with Sparse Polynomials?
###### Daniel S. Roche
Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.
more | pdf | html
None.
###### Tweets
ComputerPapers: What Can (and Can't) we Do with Sparse Polynomials?. https://t.co/0ym0V6FQUB
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6676
Unqiue Words: 2184

##### #7. Incrementally and inductively constructing basis of multiplicative dependence lattice of non-zero algebraic numbers
###### Tao Zheng
Let $x=(x_1,x_2,\cdots,x_n)^T$ be a vector of non-zero algebraic numbers, the set $\mathcal{R}_x:=\{(k_1,k_2,\cdots,k_n)^T\in\mathbb{Z}^n\;|\;x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}=1\}$ is called \emph{the multiplicative dependence lattice} of $x$. This paper develops an efficient incremental algorithm to compute a basis of $\mathcal{R}_x$. This algorithm constructs inductively a basis of the lattice as the dimension increases. This is the very first algorithm for computing the basis of the lattice, although a lot of efforts have been made to understand this lattice. In this paper we propose the conception of the \emph{rank} of a finite sequence of non-zero algebraic numbers, which turns out to be closely related to the rank of the lattice, and as well as to the complexity. The complexity of the algorithm depends not mainly on the dimension $n$ but on the rank of the sequence $x_1,x_2,\cdots,x_n$, which can be much smaller than $n$.
more | pdf | html
None.
###### Tweets
ComputerPapers: Incrementally and inductively constructing basis of multiplicative dependence lattice of non-zero algebraic numbers. https://t.co/ykwWyHXgl6
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8889
Unqiue Words: 1817

##### #8. Aligator.jl - A Julia Package for Loop Invariant Generation
###### Andreas Humenberger, Maximilian Jaroschek, Laura Kovács
We describe the Aligator.jl software package for automatically generating all polynomial invariants of the rich class of extended P-solvable loops with nested conditionals. Aligator.jl is written in the programming language Julia and is open-source. Aligator.jl transforms program loops into a system of algebraic recurrences and implements techniques from symbolic computation to solve recurrences, derive closed form solutions of loop variables and infer the ideal of polynomial invariants by variable elimination based on Gr\"obner basis computation.
more | pdf | html
None.
###### Tweets
M157q_News_RSS: Aligator.jl - A Julia Package for Loop Invariant Generation. (arXiv:1808.05394v1 [https://t.co/LljFWnr6hA]) https://t.co/Q30DI64HsF We describe the Aligator.j
###### Github

Aligator is a Mathematica software package for generating loop invariants.

Repository: aligator
User: ahumenberger
Language: Mathematica
Stargazers: 0
Subscribers: 4
Forks: 0
Open Issues: 0
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 2245
Unqiue Words: 941

##### #9. Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields
We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree $n$ over a finite field $\F_q$, the average-case complexity of our algorithm is an expected $O(n^{1 + o(1)} \log^{2 + o(1)}q)$ bit operations. Only for a negligible subset of polynomials of degree $n$ our algorithm has a higher complexity of $O(n^{4 / 3 + o(1)} \log^{2 + o(1)}q)$ bit operations. This breaks the classical $3/2$-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.
more | pdf | html
None.
###### Tweets
enclanglement: A quantum algorithm for factoring polynomials (for some reason, not posted under quant-ph). https://t.co/pxMFlBJzux
MathPaper: Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields. https://t.co/DoCDEdMpj9
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6430
Unqiue Words: 1451

##### #10. Computer algebra tools for Feynman integrals and related multi-sums
###### Johannes Blümlein, Carsten Schneider
In perturbative calculations, e.g., in the setting of Quantum Chromodynamics (QCD) one aims at the evaluation of Feynman integrals. Here one is often faced with the problem to simplify multiple nested integrals or sums to expressions in terms of indefinite nested integrals or sums. Furthermore, one seeks for solutions of coupled systems of linear differential equations, that can be represented in terms of indefinite nested sums (or integrals). In this article we elaborate the main tools and the corresponding packages, that we have developed and intensively used within the last 10 years in the course of our QCD-calculations.
more | pdf | html
###### Tweets
MathPHYPapers: Computer algebra tools for Feynman integrals and related multi-sums. https://t.co/rjdkpANStx
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7508
Unqiue Words: 1988

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 72,893 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 72,893 papers.