Top 10 Arxiv Papers Today in Symbolic Computation


0.0 Mikeys
#1. 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
#2. 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
#3. 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
#4. 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
#5. 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

0.0 Mikeys
#6. 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
#7. Bohemian Upper Hessenberg Matrices
Eunice Y. S. Chan, Robert M. Corless, Laureano Gonzalez-Vega, J. Rafael Sendra, Juana Sendra, Steven E. Thornton
We look at Bohemian matrices, specifically those with entries from $\{-1, 0, {+1}\}$. More, we specialize the matrices to be upper Hessenberg, with subdiagonal entries $\pm1$. Many properties remain after these specializations, some of which surprised us. We find two recursive formulae for the characteristic polynomials of upper Hessenberg matrices. Focusing on only those matrices whose characteristic polynomials have maximal height allows us to explicitly identify these polynomials and give a lower bound on their height. This bound is exponential in the order of the matrix. We count stable matrices, normal matrices, and neutral matrices, and tabulate the results of our experiments. We prove a theorem about the only possible kinds of normal matrices amongst a specific family of Bohemian upper Hessenberg matrices.
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 6
Total Words: 7998
Unqiue Words: 2076

0.0 Mikeys
#8. 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
#9. Computing Elimination Ideals and Discriminants of Likelihood Equations
Xiaoxian Tang, Timo De Wolff, Rukai Zhao
We develop a probabilistic algorithm for computing elimination ideals of likelihood equations, which is for larger models by far more efficient than directly computing Groebner bases or the interpolation method proposed in the first author's previous work. The efficiency is improved by a theoretical result showing that the sum of data variables appears in most coefficients of the generator polynomial of elimination ideal. Furthermore, applying the known structures of Newton polytopes of discriminants, we can also efficiently deduce discriminants of the elimination ideals. For instance, the discriminants of 3 by 3 matrix model and one Jukes-Cantor model in phylogenetics (with sizes over 30 GB and 8 GB text files, respectively) can be computed by our methods.
more | pdf | html
Figures
None.
Tweets
StatsPapers: Computing Elimination Ideals and Discriminants of Likelihood Equations. https://t.co/4dC06cDFOa
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 17165
Unqiue Words: 3179

0.0 Mikeys
#10. Towards a symbolic summation theory for unspecified sequences
Peter Paule, Carsten Schneider
The article addresses the problem whether indefinite double sums involving a generic sequence can be simplified in terms of indefinite single sums. Depending on the structure of the double sum, the proposed summation machinery may provide such a simplification without exceptions. If it fails, it may suggest a more advanced simplification introducing in addition a single nested sum where the summand has to satisfy a particular constraint. More precisely, an explicitly given parameterized telescoping equation must hold. Restricting to the case that the arising unspecified sequences are specialized to the class of indefinite nested sums defined over hypergeometric, multi-basic or mixed hypergeometric products, it can be shown that this constraint is not only sufficient but also necessary.
more | pdf | html
Figures
None.
Tweets
MathPaper: Towards a symbolic summation theory for unspecified sequences. https://t.co/UwwFmJn0JY
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 16226
Unqiue Words: 2796

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 57,756 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 57,756 papers.