Computer Algebra in Scientific Computing: 23rd International Workshop, CASC 2021, Sochi, Russia, September 13–17, 2021, Proceedings (Lecture Notes in Computer Science, 12865)

Description

This book constitutes the proceedings of the 23rd International Workshop on Computer Algebra in Scientific Computing, CASC 2021, held in Sochi, Russia, in September 2021. The 24 full papers presented together with 1 invited talk were carefully reviewed and selected from 40 submissions. The papers cover theoretical computer algebra and its applications in scientific computing. Preface Organization Contents Families of Polynomials in the Study of Biochemical Reaction Networks 1 Introduction 2 The ERK Pathway 3 Degenerations and Open Regions of Multistationarity 4 Other Computational Approaches References The m-Bézout Bound and Distance Geometry 1 Introduction 2 Bounds on the Embedding Number 3 Algebraic Systems Modeled by Simple Graphs 4 Conclusion References Computational Schemes for Subresultant Chains 1 Introduction 2 Review of Subresultant Theory 3 Computing Subresultant Chains Speculatively 4 Optimized Ducos' Subresultant Chain 5 Implementation and Experimentation 5.1 Routines over Zp[y] 5.2 Subresultants over Z[y] and Z[x,y] A Maple code for Polynomial Systems References On Rational Solutions of Pseudo-linear Systems 1 Introduction 2 Pseudo-linear Systems 3 Universal Denominators of Rational Solutions of a Single Pseudo-linear System 3.1 Existing Methods for Pure Difference and q-Difference Systems 3.2 A Unified and Efficient Approach for Pseudo-linear Systems 3.3 Computing the Dispersion Set and the Non -Fixed Part 4 Rational Solutions of Partial Pseudo-linear Systems 4.1 A Recursive Approach 4.2 Necessary Conditions for Denominators 4.3 Implementation and Comparison of Different Strategies References On the Relationship Between Differential Algebra and Tropical Differential Algebraic Geometry 1 Introduction 2 Formal Power Series Solutions of ODE 3 The Fundamental Theorem of Tropical Differential Algebraic Geometry 4 Fields of Definition and Countability 5 The Approximation Theorem 5.1 Proof of Step 1 by Ultraproducts 5.2 Proof of Step 1 by a Model Theoretic Argument 5.3 Proof of Step 1 by Lang's Infinite Nullstellensatz 5.4 Proof of Step 2 6 The New Version of the Fundamental Theorem 7 The Partial Differential Case A Basic Notions on Ultraproducts References On the Complexity and Parallel Implementation of Hensel's Lemma and Weierstrass Preparation 1 Introduction 2 Background 2.1 Power Series and Univariate Polynomials over Power Series 2.2 Weierstrass Preparation Theorem and Hensel Factorization 2.3 Parallel Patterns 3 Lazy Power Series 4 Algorithms and Complexity 4.1 Weierstrass Preparation 4.2 Hensel Factorization 5 Parallel Algorithms 5.1 Parallel Algorithms for Weierstrass Preparation 5.2 Parallel Algorithms for Hensel Factorization 6 Experimentation and Discussion References Symbolic-Numeric Algorithms for Computing Orthonormal Bases of SU(3) Group for Orbital Angular Momentum 1 Introduction 2 Algorithm of Calculating X(3)-Orthonormal G-T Basis 3 Algorithm and Calculations in Orthonormal B-M Basis 3.1 Calculations in the B-M Basis 3.2 Calculations of X(3) with Summation in the B-M Basis 4 Algorithm of Construction and Calculations of the E Basis 4.1 Calculations of X(3) in Non-orthogonal E Basis 4.2 Calculations of X(3) in Orthogonal E Basis 5 Results and Conclusions References Improved Supersingularity Testing of Elliptic Curves Using Legendre Form 1 Introduction 1.1 Supersingularity Testing Algorithms Based on Isogeny Graphs 1.2 Contributions 1.3 Related Work 2 Preliminaries 2.1 Weierstrass Curves 2.2 Legendre Form 2.3 Isogenies 3 Isogeny Volcano Graphs of Ordinary Curves 4 Composition of Fundamental Legendre Maps 5 -switching Theorem 6 Sutherland's Supersingularity Testing Algorithm 7 Our Proposed Algorithm 8 Comparison 9 Experimental Results 9.1 Computational Time in Square Root and Fourth Root 9.2 Computational Time in Supersingularity Testing Algorithm References Root Radii and Subdivision for Polynomial Root-Finding 1 Introduction 1.1 Definitions 1.2 Subdivision Approach to Root-Finding 2 Root Radii Computation 2.1 Solving the RRC* Problem 2.2 Proof of Proposition 6 2.3 Solving the RRC Problem 2.4 Implementation Details 3 Real Root Isolation 3.1 Annuli Cover and Exclusion Test 3.2 Annuli Cover and Root Counter 3.3 Annuli Cover and the RRI Problem 3.4 Experimental Results 4 Complex Root Clustering 4.1 Annuli Cover and Exclusion Test 4.2 Annuli Cover and the CRC Problem 4.3 Experimental Results References On First Integrals and Invariant Manifolds in the Generalized Problem of the Motion of a Rigid Body in a Magnetic Field 1 Introduction 2 Obtaining Integrals and Invariant Manifolds 2.1 Quadratic Integrals and Invariant Manifolds 2.2 Integrals and IMs of 3rd and 4th Degrees 3 The Equations of Motion with an Additional Quadratic Integral 3.1 Seeking Stationary Solutions and Invariant Manifolds 3.2 On the Stability of Stationary Solutions and Invariant Manifolds 4 The Equations of Motion with the Additional Integral of the 4th Degree 4.1 Seeking Stationary Solutions and Invariant Manifolds 4.2 On the Stability of Stationary Solutions and Invariant Manifolds 5 Conclusion References Automatic Differentiation with Higher Infinitesimals, or Computational Smooth Infinitesimal Analysis in Weil Algebra 1 Introduction 2 Preliminaries 3 Connection Between Automatic Differentiation and Weil Algebras 4 Algorithms 4.1 Computing C-Structure of Weil Algebra 4.2 Tensor Product of Weil Algebras 5 Examples 5.1 Higher-Order Derivatives via Dual Numbers and Higher Infinitesimals 5.2 Computation in General Weil Algebra 6 Discussions and Conclusions 6.1 Possible Applications and Related Works 6.2 Future Works A Succinct Multivariate Lazy Tower AD References On the Real Stability Radius for Some Classes of Matrices 1 Introduction 2 Algebraic Preliminaries 3 Distance to the Manifold (5) 4 Symmetric Matrix 5 Orthogonal Matrix 6 Conclusion References Decoupling Multivariate Fractions 1 Introduction 2 Decoupled and Splittable Fractions 2.1 Definitions 2.2 Characterization of Splittable Fractions 2.3 Basic Lemmas Around Fractions 2.4 Finest Decoupling Partition 2.5 Decomposition into a Sum and Product 3 Algorithm decouple 3.1 Algorithm checkC1 (F=G+H) 3.2 Algorithm checkC2 (F=c+GH) 3.3 Algorithm checkC3 (F=c+1/(G+H)) 3.4 Algorithm checkC4 (F=c+d/(1+GH)) 4 Examples 5 Implementation and Complexity 5.1 Complexity 5.2 Implementation References Towards Extending Fulton's Algorithm for Computing Intersection Multiplicities Beyond the Bivariate Case 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Local Rings and Intersection Multiplicity 2.3 Regular Sequences 2.4 Bivariate Intersection Multiplicity 2.5 A Generalization of Fulton's Properties 3 Trivariate Fulton's Algorithm 4 Generalized Fulton's Algorithm 5 Triangular Regular Sequences References On the Pseudo-Periodicity of the Integer Hull of Parametric Convex Polygons 1 Introduction 2 Preliminaries 3 The Integer Hull of an Angular Sector 4 The Integer Hull of a Convex Polygon 4.1 Case of a Triangle 4.2 Convex Polygon of Arbitrary Shape 5 Examples 6 A New Integer Hull Algorithm References Relaxed NewtonSLRA for Approximate GCD 1 Introduction 1.1 Definitions and Notations 1.2 Problem Description and SLRA 1.3 Our Contributions 2 NewtonSLRA Algorithm 3 Improvements 3.1 Subresultant Specific Better Complexity 3.2 Relaxed NewtonSLRA Algorithm 3.3 Column Weighted Frobenius Norm 4 Numerical Experiments 4.1 Subresultant Specific Better Complexity 4.2 Relaxed NewtonSLRA Algorithm 4.3 Column Weighted Frobenius Norm 4.4 Ill-Conditioned Polynomials 4.5 Polynomials with Multiple Roots References Simplification of Nested Real Radicals Revisited 1 Introduction 2 Special Polynomial Systems with Zero-Dimensional Variety of Solutions 3 Real Radicals over a Real Field 4 Simplification of Doubly Nested Real Radicals 5 Examples of Triply Nested Real Radicals over Q that Cannot Be Simplified 6 Concluding Remarks References Parametric Toricity of Steady State Varieties of Reaction Networks 1 Introduction 2 Tori Are Groups, and Shifted Tori Are Cosets 3 Real Quantifier Elimination and Simplification 4 Computational Experiments 4.1 An Artificial Triangle Network 4.2 Escherichia Coli Osmoregulation System 4.3 TGF- Pathway 4.4 N-Site Phosphorylation-Dephosphorylation Cycle 4.5 Excitatory Post-Synaptic Potential Acetylcholine Event 5 Conclusions References Testing Binomiality of Chemical Reaction Networks Using Comprehensive Gröbner Systems 1 Introduction 2 Preliminaries on Comprehensive Gröbner Systems 3 Testing Binomiality of Chemical Reaction Networks Using Comprehensive Gröbner Systems 3.1 n-Site Phosphorylation 3.2 BioModels 4 Conclusion References Primitive Recursive Ordered Fields and Some Applications 1 Introduction 2 PR Ordered Fields 3 PR Real Closure 4 PR-Archimedean Fields vs. PR Reals 5 Applications to Spectral Problems and PDEs 6 Conclusion References Exact Real Computation of Solution Operators for Linear Analytic Systems of Partial Differential Equations 1 Introduction and Summary of Contributions 2 Recap on Real Bit-Complexity Theory 2.1 Uniform Computation of Operators and Functionals 2.2 Exact Real Computation: Reliable Numerics, Conveniency 3 Computing with Power Series 4 Computing Solutions for PDEs 4.1 Cauchy-Kovalevskaya Type Linear PDEs 4.2 Polynomial-Time Solution of Analytic Heat Equation 5 Implementation 5.1 Overview of Continuous Data-Types 5.2 Power Series and Automatic Differentiation 5.3 PDE Solving 6 Conclusion References A New Deterministic Method for Computing Milnor Number of an ICIS 1 Introduction 2 Lê-Greuel Formula 3 Local Cohomology 4 Genericity 4.1 Hyperplane Sections 4.2 Auxiliary Indeterminates and Local Cohomology 5 Algorithm References New Parallelisms of PG(3,5) with Automorphisms of Order 8 1 Introduction 2 Construction Method 2.1 The Projective Space 2.2 Possible Automorphism Groups 2.3 Spread Orbits Under G8 2.4 Computer Search 3 Properties of the Obtained Parallelisms 4 Conclusion References Optimal Four-Stage Symplectic Integrators for Molecular Dynamics Problems 1 Introduction 2 Governing Equations 3 Four-Stage Symplectic Integrators 3.1 Zero Vandermonde Determinant 3.2 Nonzero Vandermonde Determinant 4 Verification of New Symplectic Integrators 5 Conclusions References On Geometric Property of Fermat–Torricelli Points on Sphere 1 Introduction 2 Algebraic Equations Derived for the Fermat–Torricelli Points 3 Solving Polynomial Equations with Parametric Coefficients Under Non-degenerate Conditions 4 Maximal Fermat–Torricelli Point on the Equator References Author Index