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.

ComputerPapers:
Algebraic number fields and the LLL algorithm. https://t.co/rglJqIMNaK

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 8961

Unqiue Words: 2005

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.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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.

Sample Sizes : None.

Authors: 1

Total Words: 27382

Unqiue Words: 2924

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
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.

Sample Sizes : None.

Authors: 1

Total Words: 18067

Unqiue Words: 4538

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
ComputerPapers:
Chordal Graphs in Triangular Decomposition in Top-Down Style. https://t.co/FaXtZFALpO

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 13699

Unqiue Words: 2421

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.

ComputerPapers:
What Can (and Can't) we Do with Sparse Polynomials?. https://t.co/0ym0V6FQUB

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 6676

Unqiue Words: 2184

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.

ComputerPapers:
Incrementally and inductively constructing basis of multiplicative dependence lattice of non-zero algebraic numbers. https://t.co/ykwWyHXgl6

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 8889

Unqiue Words: 1817

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.

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

Aligator is a Mathematica software package for generating loop invariants.

Stargazers: 0

Subscribers: 4

Subscribers: 4

Forks: 0

Open Issues: 0

Open Issues: 0

None.

Sample Sizes : None.

Authors: 3

Total Words: 2245

Unqiue Words: 941

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.

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.

Sample Sizes : None.

Authors: 1

Total Words: 6430

Unqiue Words: 1451

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
MathPHYPapers:
Computer algebra tools for Feynman integrals and related multi-sums. https://t.co/rjdkpANStx

None.

None.

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible