Computer Algebra in Scientific Computing

Frontmatter

Proof-of-Work Certificates that Can Be Efficiently Computed in the Cloud (Invited Talk)

Abstract

In an emerging computing paradigm, computational capabilities, from processing power to storage capacities, are offered to users over communication networks as a cloud-based service. There, demanding computations are outsourced in order to limit infrastructure costs.

The idea of verifiable computing is to associate a data structure, a proof-of-work certificate, to the result of the outsourced computation. This allows a verification algorithm to prove the validity of the result, faster than by recomputing it. We talk about a Prover (the server performing the computations) and a Verifier.

Goldwasser, Kalai and Rothblum gave in 2008 a generic method to verify any parallelizable computation, in almost linear time in the size of the, potentially structured, inputs and the result. However, the extra cost of the computations for the Prover (and therefore the extra cost to the customer), although only almost a constant factor of the overall work, is nonetheless prohibitive in practice.

Differently, we will here present problem-specific procedures in computer algebra, e.g. for exact linear algebra computations, that are Prover-optimal, that is that have much less financial overhead.

Jean-Guillaume Dumas

On Unimodular Matrices of Difference Operators

Abstract

We consider matrices \(L \in \mathrm{Mat} _n(K[\sigma , \sigma ^{-1}])\) of scalar difference operators, where K is a difference field of characteristic 0 with an automorphism \(\sigma \). We discuss approaches to compute the dimension of the space of those solutions of the system of equations \(L(y)=0\) that belong to an adequate extension of K. On the base of one of those approaches, we propose a new algorithm for computing \(L^{-1}\in \mathrm{Mat} _n(K[\sigma , \sigma ^{-1}])\) whenever it exists. We investigate the worst-case complexity of the new algorithm, counting both arithmetic operations in K and shifts of elements of K. This complexity turns out to be smaller than in the earlier proposed algorithms for inverting matrices of difference operators.

Some experiments with our implementation in Maple of the algorithm are reported.

S. A. Abramov, D. E. Khmelnov

Sparse Polynomial Arithmetic with the BPAS Library

Abstract

We discuss algorithms for pseudo-division and division with remainder of multivariate polynomials with sparse representation. This work is motivated by the computations of normal forms and pseudo-remainders with respect to regular chains. We report on the implementation of those algorithms with the BPAS library.

Mohammadali Asadi, Alexander Brandt, Robert H. C. Moir, Marc Moreno Maza

Computation of Pommaret Bases Using Syzygies

Abstract

We investigate the application of syzygies for efficiently computing (finite) Pommaret bases. For this purpose, we first describe a non-trivial variant of Gerdt’s algorithm [10] to construct an involutive basis for the input ideal as well as an involutive basis for the syzygy module of the output basis. Then we apply this new algorithm in the context of Seiler’s method to transform a given ideal into quasi stable position to ensure the existence of a finite Pommaret basis [19]. This new approach allows us to avoid superfluous reductions in the iterative computation of Janet bases required by this method. We conclude the paper by proposing an involutive variant of the signature based algorithm of Gao et al. [8] to compute simultaneously a Gröbner basis for a given ideal and for the syzygy module of the input basis. All the presented algorithms have been implemented in Maple and their performance is evaluated via a set of benchmark ideals.

Bentolhoda Binaei, Amir Hashemi, Werner M. Seiler

A Strongly Consistent Finite Difference Scheme for Steady Stokes Flow and its Modified Equations

Abstract

We construct and analyze a strongly consistent second-order finite difference scheme for the steady two-dimensional Stokes flow. The pressure Poisson equation is explicitly incorporated into the scheme. Our approach suggested by the first two authors is based on a combination of the finite volume method, difference elimination, and numerical integration. We make use of the techniques of the differential and difference Janet/Gröbner bases. In order to prove strong consistency of the generated scheme we correlate the differential ideal generated by the polynomials in the Stokes equations with the difference ideal generated by the polynomials in the constructed difference scheme. Additionally, we compute the modified differential system of the obtained scheme and analyze the scheme’s accuracy and strong consistency by considering this system. An evaluation of our scheme against the established marker-and-cell method is carried out.

Yury A. Blinkov, Vladimir P. Gerdt, Dmitry A. Lyakhov, Dominik L. Michels

Symbolic-Numeric Methods for Nonlinear Integro-Differential Modeling

Abstract

This paper presents a proof of concept for symbolic and numeric methods dedicated to the parameter estimation problem for models formulated by means of nonlinear integro-differential equations (IDE). In particular, we address: the computation of the model input-output equation and the numerical integration of IDE systems.

François Boulier, Hélène Castel, Nathalie Corson, Valentina Lanza, François Lemaire, Adrien Poteaux, Alban Quadrat, Nathalie Verdière

A Continuation Method for Visualizing Planar Real Algebraic Curves with Singularities

Abstract

We present a new method for visualizing planar real algebraic curves inside a bounding box based on numerical continuation and critical point methods. Since the topology of the curve near a singular point is not numerically stable, we trace the curve only outside neighborhoods of singular points and replace each neighborhood simply by a point, which produces a polygonal approximation that is \(\epsilon \)-close to the curve. Such an approximation is more stable for defining the numerical connectedness of the complement of the curve, which is important for applications such as solving bi-parametric polynomial systems.

The algorithm starts by computing three types of key points of the curve, namely the intersection of the curve with small circles centered at singular points, regular critical points of every connected component of the curve, as well as intersection points of the curve with the given bounding box. It then traces the curve starting with and in the order of the above three types of points. This basic scheme is further enhanced by several optimizations, such as grouping singular points in natural clusters and tracing the curve by a try-and-resume strategy. The effectiveness of the algorithm is illustrated by numerous examples.

Changbo Chen, Wenyuan Wu

From Exponential Analysis to Padé Approximation and Tensor Decomposition, in One and More Dimensions

Abstract

Exponential analysis in signal processing is essentially what is known as sparse interpolation in computer algebra. We show how exponential analysis from regularly spaced samples is reformulated as Padé approximation from approximation theory and tensor decomposition from multilinear algebra.

The univariate situation is briefly recalled and discussed in Sect. 1. The new connections from approximation theory and tensor decomposition to the multivariate generalization are the subject of Sect. 2. These connections immediately allow for some generalization of the sampling scheme, not covered by the current multivariate theory.

An interesting computational illustration of the above in blind source separation is presented in Sect. 3.

Annie Cuyt, Ferre Knaepkens, Wen-shin Lee

Symbolic Algorithm for Generating the Orthonormal Bargmann–Moshinsky Basis for Group

Abstract

A symbolic algorithm which can be implemented in any computer algebra system for generating the Bargmann–Moshinsky (BM) basis with the highest weight vectors of \(\mathrm {SO(3)}\) irreducible representations is presented. The effective method resulting in analytical formula of overlap integrals in the case of the non-canonical BM basis [S. Alisauskas, P. Raychev, R. Roussev, J. Phys. G 7, 1213 (1981)] is used. A symbolic recursive algorithm for orthonormalisation of the obtained basis is developed. The effectiveness of the algorithms implemented in Mathematica 10.1 is investigated by calculation of the overlap integrals for up to \(\mu =5\) with \(\lambda > \mu \) and orthonormalization of the basis for up to \(\mu =4\) with \(\lambda > \mu \). The action of the zero component of the quadrupole operator onto the basis vectors with \(\mu =4\) is also obtained.

A. Deveikis, A. A. Gusev, V. P. Gerdt, S. I. Vinitsky, A. Góźdź, A. Pȩdrak

About Some Drinfel’d Associators

Abstract

We study, by means of a fragment of theory about noncommutative differential equations, existence and unicity of Drinfel’d solutions \(G_i,i=0,1\) (with asymptotic conditions). From there, we give examples of Drinfel’d series with rational coefficients.

G. H. E. Duchamp, V. Hoang Ngoc Minh, K. A. Penson

On a Polytime Factorization Algorithm for Multilinear Polynomials over

Abstract

In 2010, Shpilka and Volkovich established a prominent result on the equivalence of polynomial factorization and identity testing. It follows from their result that a multilinear polynomial over the finite field of order 2 can be factored in time cubic in the size of the polynomial given as a string. Later, we have rediscovered this result and provided a simple factorization algorithm based on computations over derivatives of multilinear polynomials. The algorithm has been applied to solve problems of compact representation of various combinatorial structures, including Boolean functions and relational data tables. In this paper, we describe an improvement of this factorization algorithm and report on preliminary experimental analysis.

Pavel Emelyanov, Denis Ponomaryov

Tropical Newton–Puiseux Polynomials

Abstract

We introduce tropical Newton–Puiseux polynomials admitting rational exponents. A resolution of a tropical hypersurface is defined by means of a tropical Newton–Puiseux polynomial. A polynomial complexity algorithm for resolubility of a tropical curve is designed. The complexity of resolubility of tropical prevarieties of arbitrary codimensions is studied.

Dima Grigoriev

Orthogonal Tropical Linear Prevarieties

Abstract

We study the operation \(A^\perp \) of tropical orthogonalization, applied to a subset A of a vector space \(({\mathbb R}\cup \{ \infty \})^n\), and iterations of this operation. Main results include a criterion and an algorithm, deciding whether a tropical linear prevariety is a tropical linear variety formulated in terms of a duality between \(A^\perp \) and \(A^{\perp \perp }\). We give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

Dima Grigoriev, Nicolai Vorobjov

Symbolic-Numerical Algorithms for Solving Elliptic Boundary-Value Problems Using Multivariate Simplex Lagrange Elements

Abstract

We propose new symbolic-numerical algorithms implemented in Maple-Fortran environment for solving the self-adjoint elliptic boundary-value problem in a d-dimensional polyhedral finite domain, using the high-accuracy finite element method with multivariate Lagrange elements in the simplexes. The high-order fully symmetric PI-type Gaussian quadratures with positive weights and no points outside the simplex are calculated by means of the new symbolic-numerical algorithms implemented in Maple. Quadrature rules up to order 8 on the simplexes with dimension \(d=3-6\) are presented. We demonstrate the efficiency of algorithms and programs by benchmark calculations of a low part of spectra of exactly solvable Helmholtz problems for a cube and a hypercube.

A. A. Gusev, V. P. Gerdt, O. Chuluunbaatar, G. Chuluunbaatar, S. I. Vinitsky, V. L. Derbov, A. Góźdź, P. M. Krassovitskiy

Symbolic-Numeric Simulation of Satellite Dynamics with Aerodynamic Attitude Control System

Abstract

The dynamics of the rotational motion of a satellite, subjected to the action of gravitational, aerodynamic and damping torques in a circular orbit is investigated. Our approach combines methods of symbolic study of the nonlinear algebraic system that determines equilibrium orientations of a satellite under the action of the external torques and numerical integration of the system of linear ordinary differential equations describing the dynamics of the satellite. An algorithm for the construction of a Gröbner basis was implemented for determining the equilibria of the satellite for specified values of the aerodynamic torque, damping coefficients, and principal central moments of inertia. Both the conditions of the satellite’s equilibria existence and the conditions of asymptotic stability of these equilibria were obtained. The transition decay processes of the spatial oscillations of the satellite for various system parameters have also been studied.

Sergey A. Gutnik, Vasily A. Sarychev

Finding Multiple Solutions in Nonlinear Integer Programming with Algebraic Test-Sets

Abstract

We explain how to compute all the solutions of a nonlinear integer problem using the algebraic test-sets associated to a suitable linear subproblem. These test-sets are obtained using Gröbner bases. The main advantage of this method, compared to other available alternatives, is its exactness within a quite good efficiency.

M. I. Hartillo, J. M. Jiménez-Cobano, J. M. Ucha

Open Access

Positive Solutions of Systems of Signed Parametric Polynomial Inequalities

Abstract

We consider systems of strict multivariate polynomial inequalities over the reals. All polynomial coefficients are parameters ranging over the reals, where for each coefficient we prescribe its sign. We are interested in the existence of positive real solutions of our system for all choices of coefficients subject to our sign conditions. We give a decision procedure for the existence of such solutions. In the positive case our procedure yields a parametric positive solution as a rational function in the coefficients. Our framework allows to reformulate heuristic subtropical approaches for non-parametric systems of polynomial inequalities that have been recently used in qualitative biological network analysis and, independently, in satisfiability modulo theory solving. We apply our results to characterize the incompleteness of those methods.

Hoon Hong, Thomas Sturm

PDF Zum Volltext

Qualitative Analysis of a Dynamical System with Irrational First Integrals

Abstract

We conduct qualitative analysis for a completely integrable system of differential equations with irrational first integrals. These equations originate from gas dynamics and describe adiabatical motions of a compressible gas cloud with homogeneous deformation. We study the mechanical analog of this gas dynamical system – the rotational motion of a spheroidal rigid body around a fixed point in a potential force field described by an irrational function. Within our study, equilibria, pendulum oscillations and invariant manifolds, which these solutions belong to, have been found. The sufficient conditions of their stability in Lyapunov’s sense have been derived and compared with the necessary ones. The analysis has been performed with the aid of computer algebra tools which proved to be essential. The computer algebra system “Mathematica” was employed.

Valentin Irtegov, Tatiana Titorenko

Effective Localization Using Double Ideal Quotient and Its Implementation

Abstract

In this paper, we propose a new method for localization of polynomial ideal, which we call “Local Primary Algorithm”. For an ideal I and a prime ideal P, our method computes a P-primary component of I after checking if P is associated with I by using double ideal quotient (I : (I : P)) and its variants which give us a lot of information about localization of I.

Yuki Ishihara, Kazuhiro Yokoyama

A Purely Functional Computer Algebra System Embedded in Haskell

Abstract

We demonstrate how methods in Functional Programming can be used to implement a computer algebra system. As a proof-of-concept, we present the computational-algebra package. It is a computer algebra system implemented as an embedded domain-specific language in Haskell, a purely functional programming language. Utilising methods in functional programming and prominent features of Haskell, this library achieves safety, composability, and correctness at the same time. To demonstrate the advantages of our approach, we have implemented advanced Gröbner basis algorithms, such as Faugère’s \(F_4\) and \(F_5\), in a composable way.

Hiromi Ishii

Splitting Permutation Representations of Finite Groups by Polynomial Algebra Methods

Abstract

An algorithm for splitting permutation representations of a finite group over fields of characteristic zero into irreducible components is described. The algorithm is based on the fact that the components of the invariant inner product in invariant subspaces are operators of projection into these subspaces. An important part of the algorithm is the solution of systems of quadratic equations. A preliminary implementation of the algorithm splits representations up to dimensions of hundreds of thousands. Examples of computations are given in the appendix.

Vladimir V. Kornyak

Factoring Multivariate Polynomials with Many Factors and Huge Coefficients

Abstract

The standard approach to factor a multivariate polynomial in \(\mathbb {Z}[x_{1},x_{2},\dots ,x_{n}]\) is to factor a univariate image in \(\mathbb {Z}[x_{1}]\) then recover the multivariate factors from their images using a process known as multivariate Hensel lifting. For the case when the factors are expected to be sparse, at CASC 2016, we introduced a new approach which uses sparse polynomial interpolation to solve the multivariate polynomial diophantine equations that arise inside Hensel lifting.

In this work we extend our previous work to the case when the number of factors to be computed is more than 2. Secondly, for the case where the integer coefficients of the factors are large we develop an efficient p-adic method. We will argue that the probabilistic sparse interpolation method introduced by us provides new options to speed up the factorization for these two cases. Finally we present some experimental data comparing our new methods with previous methods.

Michael Monagan, Baris Tuncer

Beyond the First Class of Analytic Complexity

Abstract

We investigate the notion of analytic complexity of a bivariate holomorphic function by means of computer algebra tools. An estimate from below on the number of terms in the differential polynomials defining classes of analytic complexity is established. We provide an algorithm which allows one to explicitly compute the differential membership criteria for certain families of bivariate analytic functions in the second complexity class. The presented algorithm is implemented in the computer algebra system Singular 4-1-1.

T. M. Sadykov

A Theory and an Algorithm for Computing Sparse Multivariate Polynomial Remainder Sequence

Abstract

This paper presents an algorithm for computing the polynomial remainder sequence (PRS) and corresponding cofactor sequences of sparse multivariate polynomials over a number field \({\mathbb K}\). Most conventional algorithms for computing PRSs are based on the pseudo remainder (Prem), and the celebrated subresultant theory for the PRS has been constructed on the Prem. The Prem is uneconomical for computing PRSs of sparse polynomials. Hence, in this paper, the concept of sparse pseudo remainder (spsPrem) is defined. No subresultant-like theory has been developed so far for the PRS based on spsPrem. Therefore, we develop a matrix theory for spsPrem-based PRSs. The computational formula for PRS, regardless of whether it is based on Prem or spsPrem, causes a considerable intermediate expression growth. Hence, we next propose a technique to suppress the expression growth largely. The technique utilizes the power-series arithmetic but no Hensel lifting. Simple experiments show that our technique suppresses the intermediate expression growth fairly well, if the sub-variable ordering is set suitably.

Tateaki Sasaki

A Blackbox Polynomial System Solver on Parallel Shared Memory Computers

Abstract

A numerical irreducible decomposition for a polynomial system provides representations for the irreducible factors of all positive dimensional solution sets of the system, separated from its isolated solutions. Homotopy continuation methods are applied to compute a numerical irreducible decomposition. Load balancing and pipelining are techniques in a parallel implementation on a computer with multicore processors. The application of the parallel algorithms is illustrated on solving the cyclic n-roots problems, in particular for \(n = 8, 9\), and 12.

Jan Verschelde

Backmatter