ACM Communications in Computer Algebra

Linear recurrence equations with constant coefficients define the power series coefficients of rational functions. However, one usually prefers to have an explicit formula for the sequence of coefficients, provided that such a formula is "simple" enough. Simplicity is related to the compactness of the formula due to the presence of algebraic numbers: "the smaller, the simpler". This poster showcases the capacity of recent updates on the Formal Power Series (FPS) algorithm, implemented in Maxima and Maple (convert/FormalPowerSeries), to find simple formulas for sequences like those from https://oeis.org/A307717, https://oeis.org/A226782, or https://oeis.org/A226784 by computing power series representations of their correctly guessed generating functions. We designed the algorithm for the more general context of univariate P -recursive sequences. Our implementations are available at http://www.mathematik.uni-kassel.de/~bteguia/FPS_webpage/FPS.htm

Bertrand Teguia Tabuguia

Wolfram Koepf

ACM communications in computer algebra

FPS in action

FPS在行动

We aim to factor a sparse polynomial a ∈ Z[ x 1 , ···, x n ] represented by a black box. The authors have previously developed efficient sparse Hensel lifting algorithms for the monic and square-free case that outperforms the algorithm by Kaltofen and Trager in 1990. We complete this black box factorization problem for the non-monic case with a new algorithm that computes the factors of a using many non-monic bivariate Hensel lifts. Our algorithm handles all cases of input a ∈ Z[ x 1 , ···, x n ] including the non-square-free and the non-primitive cases. We have implemented the algorithm in Maple with all major subroutines coded in C for efficiency.

Tian Chen

Michael Monagan

Factoring non-monic polynomials represented by black boxes

分解由黑箱表示的非首一多项式

In this work, we explore the relationship between free resolution of some monomial ideals and Generalized Hamming Weights (GHWs) of binary codes. More precisely, we look for a structure smaller than the set of codewords of minimal support that provides us some information about the GHWs. We prove that the first and second generalized Hamming weight of a binary linear code can be computed (by means of a graded free resolution) from a set of monomials associated to a binomial ideal related with the code. Moreover, the remaining weights are bounded by the Betti numbers for that set.

Ignacio García-Marco

Irene Márquez-Corbella

Edgar Martínez-Moro

Yuriko Pitones

Computing generalized hamming weights of binary linear codes via free resolutions

通过自由分解计算二进制线性码的广义汉明权重的计算

We report on work-in-progress to create an SMT-solver inside Maple for non-linear real arithmetic (NRA). We give background information on the algorithm being implemented: cylindrical algebraic coverings as a theory solver in the lazy SMT paradigm. We then present some new work on the identification of minimal conflicting cores from the coverings.

AmirHosein Sadeghimanesh

Matthew England

An SMT solver for non-linear real arithmetic inside maple

Maple 中非线性实数算术的 SMT 求解器

Problem statement. Let K be a field and K be an algebraic closure of K. Consider the polynomial ring R = K[ x 1 ,..., x n ] over K and a finite sequence of polynomials f 1 ,..., f c in R with c ≤ n. Let V ⊂ K n be the algebraic set defined by the simultaneous vanishing of the f i 's. Recall that V can be decomposed into finitely many irreducible components, whose codimension cannot be greater than c. The set V c which is the union of all these irreducible components of codimension exactly c is named further the nondegenerate locus of f 1 ,..., f c .

Christian Eder

Pierre Lairez

Rafael Mohr

Mohab Safey El Din

Towards signature-based gröbner basis algorithms for computing the nondegenerate locus of a polynomial system

基于特征的Gröbner基算法在计算多项式系统非退化轨迹中的应用

In 1874 Brill and Noether designed a seminal geometric method for computing bases of Riemann-Roch spaces. From then, their method has led to several algorithms, some of them being implemented in computer algebra systems. The usual proofs often rely on abstract concepts of algebraic geometry and commutative algebra. In this paper we present a short self-contained and elementary proof that mostly needs Newton polygons, Hensel lifting, bivariate resultants, and Chinese remaindering.

Elena Berardini

Alain Couvreur

Grégoire Lecerf

A Proof of the Brill-Noether Method from Scratch

从零开始的Brill-Noether方法的证明

We consider the bit complexity of computing Chow forms of projective varieties defined over integers and their generalization to multiprojective spaces. We develop a deterministic algorithm using resultants and obtain a single exponential complexity upper bound. Earlier computational results for Chow forms were in the arithmetic complexity model; thus, our result represents the first bit complexity bound. We also extend our algorithm to Hurwitz forms in projective space and we explore connections between multiprojective Hurwitz forms and matroid theory. The motivation for our work comes from incidence geometry where intriguing computational algebra problems remain open.

M. Levent Dogan

Alperen A. Ergür

Elias Tsigaridas

On the Complexity of Chow and Hurwitz Forms

关于周形式和许尔维茨形式的复杂性

With the rise of new technologies, the demand for efficient cryptographic hardware is rising. This work is focusing on finite field based cryptography. To explore the vast design space obtained from possible finite field parameters, automated generation of hardware submodules using designer-specified algorithms for finite field arithmetic is needed. This work presents a hardware design automation framework exploiting symbolic computation capabilities of GAP to generate the expressions, needed for hardware implementations, on-the-fly, and compiles them into synthesizable datapaths, test-vectors, and testbences.

Nuša Zidarič

How to use a CAS for Hardware Design Automation

如何使用计算机代数系统进行硬件设计自动化

Cylindrical Algebraic Decomposition (CAD) is an algorithm originally proposed by Collins in [4]. Given a set of multivariate polynomials, CAD decomposes the multidimensional real space into connected subsets called cells, within which those polynomials are sign-invariant.

Tereso del Río

Clustering in the Lazard method for Cylindrical Algebraic Decomposition

Lazard方法中柱代数分解的聚类

Beamforming is a signal processing technique where an array of antenna elements can be steered to transmit and receive radio signals in a specific direction. The usage of millimeter wave (mmWave) frequencies and multiple input multiple output (MIMO) beamforming are considered as the key innovations of 5 th Generation (5G) and beyond communication systems. The mmWave radio waves enable high capacity and directive communication, but suffer from many challenges such as rapid channel variation, blockage effects, atmospheric attenuations, etc. The technique initially performs beam alignment procedure, followed by data transfer in the aligned directions between the transmitter and the receiver [1]. Traditionally, beam alignment involves periodical and exhaustive beam sweeping at both transmitter and the receiver, which is a slow process causing extra communication overhead with MIMO and massive MIMO radio units. In applications such as beam tracking, angular velocity, beam steering etc. [2], beam alignment procedure is optimized by estimating the beam directions using first order polynomial approximations. Recent learning-based SOTA strategies [3] for fast mmWave beam alignment also require exploration over exhaustive beam pairs during the training procedure, causing overhead to learning strategies for higher antenna configurations. Therefore, our goal is to optimize the beam alignment cost functions e.g. , data rate, to reduce the beam sweeping overhead by applying polynomial approximations of its partial derivatives which can then be solved as a system of polynomial equations. Specifically, we aim to reduce the beam search space by estimating approximate beam directions using the polynomial solvers. Here, we assume both transmitter (TX) and receiver (RX) to be equipped with uniform linear array (ULA) configuration, each having only one degree of freedom (d.o.f.) with N t and N r antennas, respectively.

Abbreviation	ACM Commun. Comput. Algebra
Journal Impact	0.46
Quartiles(Global)	MATHEMATICS, APPLIED(Q4)

ISSN	1932-2232, 1932-2240
h-index	12

Publication Information	Publisher: Association for Computing Machinery (ACM)，Publishing cycle: ，Journal Type: journal，Open Access Journals: No
Basic data	Year of publication: 2023，Proportion of original research papers: 100.00%，Self Citation Rate:25.00%， Gold OA Rate: 0.00%

ACM Communications in Computer Algebra

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience