Computer Algebra in Scientific Computing: 24th International Workshop, CASC 2022, Gebze, Turkey, August 22–26, 2022, Proceedings

Description

This book constitutes the proceedings of the 24th International Workshop on Computer Algebra in Scientific Computing, CASC 2022, which took place in Gebze, Turkey, in August 2022. The 20 full papers included in this book were carefully reviewed and selected from 32 submissions. They focus on the theory of symbolic computation and its implementation in computer algebra systems as well as all other areas of scientific computing with regard to their benefit from or use of computer algebra methods and software.  Preface Organization Implementation Techniques for Power, Laurent, and Puiseux Series in Several Variables (Abstract of Invited Talk) Contents Survey on Generalizations of the Intermediate Value Theorem and Applications 1 Introduction 2 Generalizations of the Intermediate Value Theorem 2.1 Definitions and Notations 2.2 Bolzano's Intermediate Value Theorem 2.3 Bolzano-Poincaré-Miranda Intermediate Value Theorem 2.4 Intermediate Value Theorem for Simplices 3 Applications of the Intermediate Value Theorems 3.1 Bisection Method 3.2 Generalized Bisection Methods 3.3 Generalized Method of Bisection for Simplices 3.4 Locating and Computing Periodic Orbits 4 Synopsis References On Truncated Series Involved in Exponential-Logarithmic Solutions of Truncated LODEs 1 Introduction 2 Truncated Equations 3 Truncated Solutions 4 The Case of Exponential-Logarithmic Solutions 5 Automatic Confirmation of the Solutions Truncation Degree Maximality 6 Conclusion References Subresultant Chains Using Bézout Matrices 1 Introduction 2 Fraction-Free LU Decomposition 2.1 Smart-Pivoting in FFLU Algorithm 2.2 Parallel FFLU Algorithm 2.3 Experimentation 3 Bézout Subresultant Algorithms 3.1 Bézout Matrix and Subresultants 3.2 Speculative Bézout Subresultant Algorithms 3.3 Experimentation References Application of Symbolic-Numerical Modeling Tools for Analysis of Gyroscopic Stabilization of Gyrostat Equilibria 1 Introduction 2 Construction of a Symbolic Model and Stability Conditions 3 Parametric Analysis 3.1 Investigated Relative Equilibrium Positions 3.2 The Gyroscopic Stabilization of Equilibrium (5) 3.3 The Gyroscopic Stabilization of Equilibrium (6) 4 Conclusion References Computer Science for Continuous Data 1 Introduction and Motivation 2 Computable Continuous Data Types 2.1 Formal Numerical Software Engineering 2.2 Kleene Logic Data Type, Generalized Sierpiński Topology 2.3 Enrichment/Promises 2.4 Multivaluedness/Non-extensionality 2.5 Examples 2.6 More Continuous Data Types 3 New Numerical Programming 3.1 Analytic Programming 3.2 Implementations 3.3 Example ERC Programs 3.4 Advanced and Upcoming ERC Programs 3.5 Verification/Testing 4 Coding Theory 4.1 Quantitative Coding Theory of Compact Metric Spaces 4.2 Encoding Advanced Spaces in Analysis 5 Complexity Theory of Continuous Data 5.1 Computational Complexity of Continuous Data 5.2 Algorithmic Random Sampling of Continuous Data 6 From Theory to Applications via Practice 6.1 Software Library 6.2 Hardware Acceleration 6.3 User Interface 6.4 Computer Analysis System 6.5 Experimental Transcendental Mathematics References Computational Aspects of Equivariant Hilbert Series of Canonical Rings for Algebraic Curves 1 Introduction 1.1 Equivariant Hilbert Series 1.2 Petri's Theorem 2 Equivariant Hilbert Series of Canonical Rings 3 The Case of Fermat Curves 3.1 The Polynomials fQ,V(T) 3.2 The Polynomials fQ0,V(T) 3.3 The Polynomials fQ1,V(T) 4 Implementation and Examples 5 Appendix - The Ramification Data of Fermat Curves References Symbolic-Numeric Algorithm for Calculations in Geometric Collective Model of Atomic Nuclei 1 Introduction 2 The Statement of the Problem and Subroutines 2.1 The Representation of the Wave Functions in Coordinate Space 2.2 -Dependent Part of the Basis States 2.3 Wave Function for Degree of Freedom KL() 2.4 Gram–Schmidt Orthogonalization of the Functions KL() 2.5 The Normalized Components Fn() 2.6 Hamiltonian Matrix Elements and Algebraic Eigenvalue Problem 2.7 Matrix Elements "426830A '' L | cosm(3) | L "526930B 2.8 Matrix Elements "426830A '' | | "526930B 3 Benchmark Calculations of GCM for 186Os Nucleus 3.1 The Example of Calculations of Eigenenergies ELn (in MeV) 3.2 The Quadrupole Moment Q and Transitions B(E2) 3.3 Matrix Elements [2]n2,n1(L2,L1) and [[2][2]][2]n2,n1(L2,L1) 3.4 Matrix Elements "426830A 11L1 | [2] | 22L2 "526930B 3.5 Matrix Elements "426830A 11L1 | [[2][2]][2] | 22L2 "526930B 3.6 An Example of Calculations of The Qn(L)(in eb) of 186Os 3.7 An Example of Calculations of the B(E2) (in e2b2) of 186Os 3.8 Finding the Optimal Basis Parameters ch7Troltenier1991 4 Conclusions A Appendix. Sets of Input Parameters for Atomic Nuclei B Appendix. Boundary Value Problem for GCM Model References Analyses and Implementations of Chordality-Preserving Top-Down Algorithms for Triangular Decomposition 1 Introduction 2 Preliminaries 2.1 Triangular Set and Triangular Decomposition 2.2 Sparse Triangular Decomposition Based on Chordal Graphs 3 Chordality in Top-Down Triangular Decomposition 4 When is the Chordality Destroyed? 4.1 Simplifying a Polynomial Set with Its Binomials 4.2 Simplifying a Polynomial System with Binomials 4.3 Reducing Inequation Polynomials with a Polynomial in the Triangular Set 4.4 Reducing a Triangular System with a Polynomial in the Triangular Set 4.5 Analysis on the Four Operations 5 Chordality-Preserving Implementations and Experiments 5.1 Removing Chordality-Destroying Operations 5.2 Further Optimization with Dynamic Checking 5.3 Chordality-Preserving Implementations for SimSer and TriSer Functions 6 Concluding Remarks and Future Work References Accelerated Subdivision for Clustering Roots of Polynomials Given by Evaluation Oracles 1 Introduction 1.1 Our Contributions 1.2 Related Work 1.3 Structure of the Paper 1.4 Definitions and Two Evaluations Bounds 2 Power Sums and Cauchy Sums 2.1 Approximation of the Power Sums 2.2 Computation of Cauchy Sums 2.3 Approximating the Power Sums s0,s1, …, sh 3 Exclusion Test and Root Counters 3.1 Root Counting with Known Isolation 3.2 Cauchy Exclusion Test 3.3 Cauchy Root Counter 4 Root Radii Algorithms 4.1 Approximation of the Largest Root Radius 4.2 Approximation of the (d+1-m)-th Root Radius 5 A Compression Algorithm 6 Two Cauchy Root Finders 6.1 Subdivision Loop 6.2 Output Verification 7 Experiments 8 Conclusion References On Equilibrium Positions in the Problem of the Motion of a System of Two Bodies in a Uniform Gravity Field 1 Introduction 2 The Lagrange Function and the Equations of Motion 3 Finding Stationary Solutions and IMs 3.1 The Usage of Stationary Conditions 3.2 The Usage of the Equations of Motion 4 On the Stability of Solutions 5 Conclusion References An Interpolation Algorithm for Computing Dixon Resultants 1 Introduction 2 Dixon Resultants 3 Modified Interpolation Using Kronecker Substitution 3.1 Partial Degrees of A=f/g in Each Variable 3.2 Algorithm by Cuyt and Lee 3.3 Kronecker Substitution 3.4 Bad Evaluation Points 4 The Dixon Resultant Algorithm 5 Implementation Notes and Benchmarks 5.1 Speeding Up Evaluation of the Dixon Matrix 5.2 Timings 6 Conclusion References Distance Evaluation to the Set of Matrices with Multiple Eigenvalues 1 Introduction 2 Algebraic Preliminaries 3 Distance Equation and Perturbation Matrix 4 Singular Values 5 Distance via Matrix Eigenvalues 5.1 Symmetric Matrix 5.2 Skew-Symmetric Matrix 5.3 Orthogonal Matrix 6 Conclusions References On Boundary Conditions Parametrized by Analytic Functions 1 Introduction 2 Gaussian Processes 3 Solution Sets of Operator Equations 4 Parametrizations 5 Rings of Differential Operators over Differential Algebras 6 Module-Theoretic Constructions 7 Parametrizing Boundary Conditions 7.1 Boundary Conditions for Function Values of Single Functions 7.2 Boundary Conditions for Derivatives and Vectors 8 Examples References Computing the Integer Hull of Convex Polyhedral Sets 1 Introduction 2 Preliminaries 3 Two Core Constructions of our Algorithm 3.1 Normalization 3.2 Partitioning 4 Integer Hull of a 2D Polyhedral Set 4.1 Algorithm 4.2 An Example 5 Integer Hull of a 3D Polyhedral Set 5.1 Algorithm 6 Implementation and Experimentation 6.1 The Maple Implementation 6.2 The C/C++ Implementation 7 Conclusion and Future Work References A Comparison of Algorithms for Proving Positivity of Linearly Recurrent Sequences 1 Introduction 2 Preliminaries 2.1 Linear Recurrence Sequences 2.2 Characteristic Polynomial 2.3 Positivity 3 Algorithms 3.1 Algorithm 1 3.2 Algorithm 2 3.3 D-finite Reduction 3.4 Classical Algorithm for Sequences with Unique Dominant Eigenvalue 3.5 Combination of Algorithm 1 and Algorithm 2 3.6 Decomposition into Non-degenerate Sequences 4 Comparison 4.1 Test Set 4.2 SageMath Implementation 4.3 Mathematica Implementation 5 Conclusions References Stability Analysis of Periodic Motion of the Swinging Atwood Machine 1 Introduction 2 Model Description 3 Periodic Solution 4 Stability Analysis 4.1 Computing the Monodromy Matrix 4.2 Characteristic Multipliers 5 Conclusion References New Heuristic to Choose a Cylindrical Algebraic Decomposition Variable Ordering Motivated by Complexity Analysis 1 Introduction 1.1 Cylindrical Algebraic Decomposition 1.2 CAD Variable Ordering 1.3 Plan of the Paper 2 Previous Heuristics 2.1 The Brown Heuristic 2.2 The sotd Heuristics 3 Our New Proposed Heuristics 3.1 Heuristic Motivated by a Complexity Analysis: mods 3.2 Creating a Greedy Version of mods 3.3 Heuristic Motivated by Expected Number of Cells 4 Experiments and Benchmarking 4.1 Benchmarking 4.2 Evaluation Metrics 4.3 Metrics and Expensive Heuristics 5 Results and Analysis 5.1 Expensive Heuristics: sotd vs mods 5.2 Cheaper Heuristics: gmods vs brown 5.3 Expensive vs Cheap Approach: mods vs gmods 6 Final Thoughts 6.1 Conclusions 6.2 Future Work References An Implementation of Parallel Number-Theoretic Transform Using Intel AVX-512 Instructions 1 Introduction 2 Number-Theoretic Transform (NTT) 3 Vectorization of NTT Kernels 4 Parallel Implementation of Number-Theoretic Transform 5 Performance Results 6 Conclusion References Locating the Closest Singularity in a Polynomial Homotopy 1 Introduction 2 Monomial Homotopies 2.1 A Square Root Homotopy 2.2 Two Paths Ending in a Cusp 2.3 A Random 4-Dimensional Monomial Homotopy 3 Asymptotic Expansions 4 Fourier Series 5 Polynomial Homotopies 5.1 The Last Pole 5.2 Homotopy Reconditioning 6 Computational Experiments 6.1 Ojika's First Example 6.2 One Fourfold Root of Cyclic 9-Roots 7 Conclusions References A General Method of Finding New Symplectic Schemes for Hamiltonian Mechanics 1 Introduction 2 Governing Equations 3 Symplectic Partitioned Runge–Kutta Schemes 4 Forest–Ruth Scheme 4.1 The General Case 5 Kepler's Problem 6 Conclusions References A Mechanical Method for Isolating Locally Optimal Points of Certain Radical Functions 1 Introduction 2 Quadratic Local Upper Bound of Polynomials 3 Local Critical Analysis of Rational and Radical Functions 3.1 Rational Functions 3.2 Sum of Radicals 4 Local Critical Analysis of the Spherical Six-Point Problem References Author Index