Computer Algebra in Scientific Computing

Let \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}\) be an algebraic number field. In 2023, Ansari and Monagan designed a modular algorithm to compute the monic gcd g of two polynomials \(f_1\) and \(f_2\) in \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}[x_1,\ldots ,x_k]\). The algorithm computes g modulo primes and uses interpolation to recover \(x_2,x_3,\dots ,x_k\) in g. However, the algorithm may fail in certain cases, for instance, when encountering a zero divisor. In this paper, we present a refined classification of failure cases for this algorithm and provide a detailed analysis of their probabilities.

We develop a unified second-order parameterized complexity theory for spaces of integrable functions. This generalizes the well-established case of continuous functions. Specifically, we prove the mutual linear equivalence of three natural parameterizations of the space \(\textrm{L}^{p}\) of p-integrable complex functions on the real unit interval: (binary) \(\textrm{L}^{p}\)-modulus, rate of convergence of Fourier series, and rate of approximation by step functions.

We refine known facts about primitive recursive ordered fields to Grzegorczyk’s classes \(\mathcal {E}^n\) for every \(n\geqslant 3\), and prove some results specific for the ordered fields in these classes. In particular, we prove versions of \(\mathcal {E}^n\)-quantifier-elimination for real closed fields and of the \(\mathcal {E}^n\)-computability of the real closure of an \(\mathcal {E}^n\)-ordered field, study the splitting and root-finding properties of \(\mathcal {E}^n\)-computable ordered fields, establish relationships between \(\mathcal {E}^n\)-computable ordered fields of reals and the field of \(\mathcal {E}^n\)-computable reals, state the \(\mathcal {E}^n\)-computability of spectral decompositions, and show that the introduced hierarchies of ordered fields do not collapse.

The definition of Stirling numbers for complex arguments proposed by Flajolet & Prodinger is studied. Stirling numbers are defined by contour integrals in the complex plane. In addition to symbolic special cases, methods for evaluating the integrals numerically are presented. Numerical integration methods based on exponentially convergent trapezoidal schemes are implemented; optimizations of the calculations are explored.

We present f4ncgb, a new open-source C++ library for Gröbner basis computations in free algebras, which transfers recent advancements in commutative Gröbner basis software to the noncommutative setting. As our experiments show, f4ncgb establishes a new state of the art for noncommutative Gröbner basis computations. We also discuss implementation details and design choices.

Initial Orbit Determination (IOD) is the classical problem of estimating the orbit of a body in space without any presumed information about the orbit. The geometric formulation of the “angles-only” IOD in three-dimensional space: find a conic curve with a given focal point meeting the given lines of sight (LOS).

We provide an algebraic reformulation of this problem and confirm that five is the minimal number of lines necessary to have a finite number of solutions in a non-special case, and the number of complex solutions is 66.

We construct a subdivision method to search for the normal direction to the orbital plane as a point on the real projective plane. The resulting algorithm is fast as it discovers only a handful of the solutions that are real and physically meaningful.

The problem of a balanced dynamically asymmetric ball with a rotor rolling without slipping on an unmoving horizontal absolutely rough plane in a uniform gravity field is considered. Using the methods of computer algebra, we conduct the qualitative analysis of the equations of motion of the body: invariant sets satisfying the necessary conditions for the extremum of the problem’s first integrals are found, and their Lyapunov stability is studied. A mechanical interpretation of the solutions obtained is given.

Hilbert’s Irreducibility Theorem states that for a parametric irreducible polynomial f(A, X) of \(\mathbb {Q}[A,X]\) with parameters \(A=\{a_1,\ldots ,a_m\}\) and indeterminates \(X=\{x_1,\ldots ,x_n\}\), the set \(\mathcal {O}_f=\{\alpha \in \mathbb {Q}^m \mid f(\alpha ,X) \text { is irreducible over }\mathbb {Q}\}\) forms a dense subset of \(\mathbb {Q}^m\) in the Euclidean topology, where \(\mathcal {O}_f\) is called a basic Hilbert subset w.r.t. f. We generalize this theorem to a prime or primary ideal P of \(\mathbb {Q}[A,X]\) and propose an effective method to compute a Hilbert subset \(\mathcal {O}\) in \(\mathbb {Q}^m\) such that P preserves its primality or primariness over \(\mathcal {O}\) when \(P\cap \mathbb {Q}[A]=\{0\}\), i.e., there are no algebraic constraints between parameters. To explain more explicitly, we consider the specialization map \(\varphi _\alpha :f(A,X)\mapsto f(\alpha ,X)\) for \(\alpha \in \mathbb {Q}^m\). For a prime (primary) ideal P of \(\mathbb {Q}[A,X]\) with \(P\cap \mathbb {Q}[A]=\{0\}\), our algorithm computes an irreducible polynomial f in \(\mathbb {Q}[A,X]\) and a parametric ideal J of \(\mathbb {Q}[A]\) such that \(\varphi _\alpha (P)\) is a prime (primary) ideal for any \(\alpha \in \mathcal {O}=\mathcal {O}_f\cap (\mathbb {Q}^m\setminus V_{\mathbb {Q}}(J))\), where \(V_{\mathbb {Q}}(J)\) denotes the set of zeros of J in \(\mathbb {Q}^m\). In addition, our method can be applied to a primary ideal Q with \(Q\cap \mathbb {Q}[A]\not =\{0\}\) if \(Q\cap \mathbb {Q}[A]\) is a prime ideal. In this case, \(\varphi _\alpha (Q)\) is a primary ideal for any \(\alpha \in \mathcal {O}_f\cap (V_{\mathbb {Q}}(Q\cap \mathbb {Q}[A])\setminus V_{\mathbb {Q}}(J))\), which we call a semi-Hilbert subset for Q. We implement our algorithm on the computer algebra system Risa/Asir and present its applications including parametric primary decomposition.

Numerous important integrals involve products of the Fox H-functions and their particular cases. The most comprehensive and universal method for calculating integrals of a single Fox H-function or the product of two Fox H-functions has been developed by O.I. Marichev and has been implemented in Wolfram Mathematica computer algebra system. However, as of now, no general method for finding integrals of the product of three or more Fox H-functions has been implemented in any computer algebra system. This method, based on calculation of multidimensional residues, is the subject of the present article.

Neural networks are important tools in machine learning. Representing piecewise linear activation functions with tropical arithmetic enables the application of tropical geometry. Algorithms are presented to compute regions where the neural networks are linear maps. Through computational experiments, we provide insights on the difficulty to train neural networks, in particular on the problems of overfitting and on the benefits of skip connections.

The basic Schoof algorithm provides an efficient method for computing the trace of an endomorphism \(\phi \) of an elliptic curve E. It collects small primes \(\ell \) whose product exceeds \(4\sqrt{\deg (\phi )}\), and computes the trace of \(\phi \) modulo each \(\ell \) by working over the \(\ell \)-torsion subgroup of E. For a supersingular elliptic curve E defined over \(\mathbb {F}_{p^2}\), it is efficient to randomly sample a point on E of order \(\ell \), provided that \(\ell \) divides the order of the group of \(\mathbb {F}_{p^{2e}}\)-rational points on E for some small extension degree e. In this paper, we incorporate the random sampling method as a subroutine within Schoof’s algorithm and analyze its heuristic complexity. Furthermore, we combine the random sampling method with additional techniques, such as the use of kernel polynomials, to further accelerate Schoof’s algorithm on supersingular elliptic curves. We demonstrate the effectiveness of our hybrid approach through experimental results.

We present a new black box GCD algorithm for two multivariate polynomials a and b in \(\mathbb {Z}[x_1,x_2,\dots ,x_n]\) where a and b are input as black boxes for their evaluation. Our algorithm computes \(g = \gcd (a,b)\) in the sparse representation using sparse Hensel lifting from bivariate images of g. More precisely, our algorithm first computes the square-free factorization of the primitive part of g in \(x_1\) and then, optionally, computes the content of g in \(x_1\) recursively.

We have implemented our new algorithm in Maple with parts of it coded in C for increased efficiency. For comparison, we have implemented the Kaltofen–Diaz black box GCD algorithm and also a black box GCD algorithm constructed from the Kaltofen–Yang sparse rational function interpolation algorithm. Our experimental results show that our new algorithm is always competitive with the Kaltofen–Yang and Kaltofen–Diaz algorithms and faster when the square-free factors of g are smaller than g or we do not need the content of g in \(x_1\).

In 2022, Moriya, Onuki, Aikawa, and Takagi proposed a new framework named generalized Montgomery coordinates to treat one-coordinate type formulas to compute isogenies. This framework generalizes some already known one-coordinate type formulas of elliptic curves. Their result shows that a formula to compute image points under isogenies is unique in the framework of generalized Montogmery coordinates; however, a formula to compute image curves is not unique. Therefore, we have a question: What formula is the most efficient to compute image curves in the framework of generalized Montogmery coordinates?

In this paper, we analyze the costs of formulas to compute image curves of 3-isogenies in the framework of generalized Montgomery coordinates. From our result, the lower bound of the costs is \(1\textbf{M}+1\textbf{S}\) as a formula whose output and input are in affine coordinates, \(2\textbf{S}\) as an affine formula whose output is projective, and \(2\textbf{M}+3\textbf{S}\) as a projective formula.

We study an important special case of the differential elimination problem: given a polynomial parametric dynamical system \({{\,\mathrm{\textbf{x}}\,}}' = {{\,\mathrm{\textbf{g}}\,}}({{\,\mathrm{\boldsymbol{\mu }}\,}}, {{\,\mathrm{\textbf{x}}\,}})\) and a polynomial observation function \(y = f({{\,\mathrm{\boldsymbol{\mu }}\,}},{{\,\mathrm{\textbf{x}}\,}})\), find the minimal differential equation satisfied by y. In our previous work [29], for the case \(y = x_1\), we established a bound on the support of such a differential equation for the non-parametric case and showed that it can be turned into an algorithm via the evaluation-interpolation approach. The main contribution of the present paper is a generalization of the aforementioned result in two directions: to allow any polynomial function \(y = f({{\,\mathrm{\textbf{x}}\,}})\), not just a single coordinate, and to allow \({{\,\mathrm{\textbf{g}}\,}}\) and f to depend on unknown symbolic parameters. We conduct computation experiments to evaluate the accuracy of our new bound and show that the approach allows to perform elimination for some cases out of reach for the state of the art software.

We have been involved in the creation of multiple software systems for computer algebra, including Reduce, Maple, Axiom and Aldor as well as a number of smaller specialised programs. We relate observations on how the meaning of software portability has changed over time and how it continues to evolve. We describe how the systems with which we have first-hand experience have achieved portability, how the central issues have changed over time and the challenges that remain.

An effective method for optimizing path planning for a specific model of a 6-degree-of-freedom (6-DOF) robot manipulator is presented as part of the motion planning of the manipulator using computer algebra. We assume that we are given a path in the form of a set of line segments that the end-effector should follow. We also assume that we have a method to solve the inverse kinematic problem of the manipulator at each via-point of the trajectory. The proposed method consists of three steps. First, we calculate the feasible region of the manipulator under a specific configuration of the end-effector. Next, we aim to find a trajectory on the line segments and a sequence of joint configurations the manipulator should follow to move the end-effector along the specified trajectory. Finally, we find the optimal combination of solutions to the inverse kinematic problem at each via-point along the trajectory by reducing the problem to a shortest-path problem of the graph and applying Dijkstra’s algorithm. We show the effectiveness of the proposed method by experiments.

We propose an effective method for solving the inverse kinematic problem of a specific model of 6-degree-of-freedom (6-DOF) robot manipulator using computer algebra. It is known that when the rotation axes of three consecutive rotational joints of a manipulator intersect at a single point, the inverse kinematics problem can be divided into determining position and orientation. We extend this method to more general manipulators in which the rotational axes of two consecutive joints intersect. This extension broadens the class of 6-DOF manipulators for which the inverse kinematics problem can be solved, and is expected to enable more efficient solutions. The inverse kinematic problem is solved using the Comprehensive Gröbner System (CGS) with joint parameters of the robot appearing as parameters in the coefficients to prevent repetitive calculations of the Gröbner bases. The effectiveness of the proposed method is shown by experiments.

Triangular decomposition algorithms that preserve chordal structure have proven effective for solving sparse polynomial systems. Additionally, choosing perfect elimination orderings plays an important role in the performance of sparse triangular decomposition, as different orderings can lead to significantly different computational costs. In this paper, we theoretically demonstrate that all the other variables that may occur in the intermediate polynomials generated during the elimination process started from polynomials with leading variable \(x_i\) are confined to the path from the node \(x_i\) to the root node in the elimination tree. This property not only relaxes certain assumptions previously required in complexity analyses of triangular decomposition algorithm over \(\mathbb {F}_2\) based on chordal graphs, but also provides a new heuristic aimed at selecting perfect elimination orderings for a class of triangular decomposition algorithms. The key idea of the proposed heuristic is to reduce the number of variable elimination by minimizing the average height of the corresponding elimination tree, which is defined as the ratio of the sum of the distances from all nodes to the root to the total number of nodes. Experimental results show that the elimination orderings generated by our proposed algorithm lead to improved efficiency in computing sparse triangular decompositions.

We propose a parallel algorithm for computing the power series solutions to an arbitrary linear ordinary differential equation with power series coefficients at one of its ordinary points. We take advantage of a tiling strategy. Our experimental results show that the proposed algorithm achieves significant speedup factors with respect to its serial counterpart as well as to other serial implementation solving the same problem. The code we developed is part of the Basic Polynomial Algebra Subprograms (BPAS) and is publicly available.

In this paper, we propose two novel formulations for computing the subresultants of two Bernstein polynomials. Specifically, we derive subresultants under Bernstein basis in (i) determinant form and (ii) determinant polynomial form. To this end, we introduce two new subresultant matrices for Bernstein polynomials, whose determinant (for the first form) or determinant polynomial (for the second form) yields the subresultant of their standard monomial expansions. Notably, the resulting subresultant inherently retains the Bernstein form when expressed in polynomial form. The equivalence of these formulas to the standard monomial-basis one is rigorously established. Furthermore, we demonstrate an application of the proposed formulas in computing the GCD of parametric Bernstein polynomials. Unlike conventional methods, our approach avoids basis transformation, thereby eliminating numerical instability arising from such transformations.

We discuss several applications of the polynomials associated with matrices of Hankel structure. These are the problem of localization of zeros of a univariate polynomial, rational interpolation problem, and the problem of systematic errors detection in the data set. Some results originated by Jacobi are modernized with constructive computational procedures.