Top 10 Arxiv Papers Today in Symbolic Computation


0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: Algebraic number fields and the LLL algorithm. https://t.co/rglJqIMNaK
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8961
Unqiue Words: 2005

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 27382
Unqiue Words: 2924

0.0 Mikeys
#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
Figures
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…
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 18067
Unqiue Words: 4538

0.0 Mikeys
#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
Figures
Tweets
ComputerPapers: Chordal Graphs in Triangular Decomposition in Top-Down Style. https://t.co/FaXtZFALpO
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 13699
Unqiue Words: 2421

0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: What Can (and Can't) we Do with Sparse Polynomials?. https://t.co/0ym0V6FQUB
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6676
Unqiue Words: 2184

0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: Incrementally and inductively constructing basis of multiplicative dependence lattice of non-zero algebraic numbers. https://t.co/ykwWyHXgl6
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8889
Unqiue Words: 1817

0.0 Mikeys
#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
Figures
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
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 2245
Unqiue Words: 941

0.0 Mikeys
#9. Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields
Javad Doliskani
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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6430
Unqiue Words: 1451

0.0 Mikeys
#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
Figures
Tweets
MathPHYPapers: Computer algebra tools for Feynman integrals and related multi-sums. https://t.co/rjdkpANStx
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7508
Unqiue Words: 1988

About

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
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 72,893 papers.