Computational Mathematics with SageMath

Description

SageMath, or Sage for short, is an open-source mathematical software system based on the Python language and developed by an international community comprising hundreds of teachers and researchers, whose aim is to provide an alternative to the commercial products Magma, Maple, Mathematica, and MATLAB®. To achieve this, Sage relies on many open-source programs, including GAP, Maxima, PARI, and various scientific libraries for Python, to which thousands of new functions have been added. Sage is freely available and is supported by all modern operating systems. Sage provides a wonderful scientific and graphical calculator for high school students, and it efficiently supports undergraduates in their computations in analysis, linear algebra, calculus, etc. For graduate students, researchers, and engineers in various mathematical specialties, Sage provides the most recent algorithms and tools, which is why several universities around the world already use Sage at the undergraduate level. Computational Mathematics with SageMath, written by researchers and by teachers at the high school, undergraduate, and graduate levels, focuses on the underlying mathematics necessary to use Sage efficiently and is illustrated with concrete examples. Part I is accessible to high school and undergraduate students and Parts II, III, and IV are suitable for graduate students, teachers, and researchers. This book is available under a Creative Commons license at sagebook.gforge.inria.fr. I Getting to Grips with Sage First Steps The Sage Program A Tool for Mathematics Sage as a Calculator First Computations Elementary Functions and Usual Constants On-Line Help and Automatic Completion Python Variables Symbolic Variables First Graphics Analysis and Algebra Symbolic Expressions and Simplification Symbolic Expressions Transforming Expressions Usual Mathematical Functions Assumptions Some Pitfalls Equations Explicit Solving Equations with no Explicit Solution Analysis Sums Limits Sequences Power Series Expansions Series Derivatives Partial Derivatives Integrals Basic Linear Algebra Solving Linear Systems Vector Computations Matrix Computations Reduction of a Square Matrix Programming and Data Structures Syntax General Syntax Function Calls More About Variables Algorithmics Loops Conditionals Procedures and Functions Example: Fast Exponentiation Input and Output Lists and Other Data Structures List Creation and Access Global List Operations Main Methods on Lists Examples of List Manipulations Character Strings Shared or Duplicated Data Structures Mutable and Immutable Data Structures Finite Sets Dictionaries Graphics 2D Graphics Graphical Representation of a Function Parametric Curve Curve in Polar Coordinates Curve Defined by an Implicit Equation Data Plot Displaying Solutions of Differential Equations Evolute of a Curve 3D Curves Computational Domains Sage is Object-Oriented Objects, Classes and Methods Objects and Polymorphism Introspection Elements, Parents, Categories Elements and Parents Constructions Further Reading: Categories Domains with a Normal Form Elementary Domains Compound Domains Expressions vs Computational Domains Symbolic Expressions as a Computational Domain Examples: Polynomials and Normal Forms Example: Polynomial Factorisation Synthesis II Algebra and Symbolic Computation Finite Fields and Number Theory Finite Fields and Rings The Ring of Integers Modulo n Finite Fields Rational Reconstruction The Chinese Remainder Theorem Primality Factorisation and Discrete Logarithms Applications The Constant delta Computation of a Multiple Integral Polynomials Polynomial Rings Introduction Building Polynomial Rings Polynomials Euclidean Arithmetic Divisibility Ideals and Quotients Factorisation and Roots Factorisation Root Finding Resultant Galois Group Rational Functions Construction and Basic Properties Partial Fraction Decomposition Rational Reconstruction Formal Power Series Operations on Truncated Power Series Solutions of an Equation: Series Expansions Lazy Power Series Computer Representation of Polynomials Linear Algebra Elementary Constructs and Manipulations Spaces of Vectors and Matrices Vector and Matrix Construction Basic Manipulations and Arithmetic on Matrices Basic Operations on Matrices Matrix Computations Gaussian Elimination, Echelon Form Linear System Solving, Image and Nullspace Basis Eigenvalues, Jordan Form and Similarity Transformation Polynomial Systems Polynomials in Several Variables The Rings A[x1,...,xn] Polynomials Basic Operations Arithmetic Polynomial Systems and Ideals A First Example What Does Solving Mean? Ideals and Systems Elimination Zero-Dimensional Systems Gröbner Bases Monomial Orders Division by a Family of Polynomials Gröbner Bases Gröbner Basis Properties Computations Differential Equations and Recurrences Differential Equations Introduction First-Order Ordinary Differential Equations Second-Order Equations The Laplace Transform Systems of Linear Differential Equations Recurrence Relations Recurrences u(n+1) = f(u(n)) Linear Recurrences with Rational Coefficients Non-Homogeneous Linear Recurrence Relations III Numerical Computation Floating-Point Numbers Introduction Definition Properties and Examples Standardisation The Floating-Point Numbers Which Kind of Floating-Point Numbers to Choose? Properties of Floating-Point Numbers These Sets are Full of Gaps Rounding Some Properties Complex Floating-Point Numbers Methods Interval and Ball Arithmetic Implementation in Sage Computing with Real Intervals and Real Balls Some Examples of Applications Complex Intervals and Complex Balls Usage and Limitations Interval Arithmetic is Used by Sage Conclusion Non-Linear Equations Algebraic Equations The Method Polynomial.roots() Representation of Numbers The Fundamental Theorem of Algebra Distribution of the Roots Solvability in Radicals The Method Expression.roots() Numerical Solution Location of Solutions of Algebraic Equations Iterative Approximation Methods Numerical Linear Algebra Inexact Computations Matrix Norms and Condition Number Dense Matrices Solving Linear Systems Direct Resolution The LU Decomposition The Cholesky Decomposition The QR Decomposition Singular Value Decomposition Application to Least Squares Eigenvalues, Eigenvectors Polynomial Curve Fitting: the Devil is Back Implementation and Efficiency Sparse Matrices Where do Sparse Systems Come From? Sparse Matrices in Sage Solving Linear Systems Eigenvalues, Eigenvectors More Thoughts on Solving Large Non-Linear Systems Numerical Integration Numerical Integration Available Integration Functions Multiple Integrals Solving Differential Equations An Example Available Functions IV Combinatorics Enumeration and Combinatorics Initial Examples Poker and Probability Enumeration of Trees Using Generating Functions Common Enumerated Sets First Example: Subsets of a Set Integer Partitions Some Other Finite Enumerated Sets Set Comprehension and Iterators Constructions Generic Algorithms Lexicographic Generation of Lists of Integers Integer Points in Polytopes Species, Decomposable Combinatorial Classes Objects up to Isomorphism Graph Theory Constructing Graphs Starting from Scratch Available Constructors Disjoint Unions Graph Visualisation Methods of the Graph Class Modification of Graph Structure Operators Graph Traversal and Distances Flows, Connectivity, Matching NP-Complete Problems Recognition and Testing of Properties Graphs in Action Greedy Vertex Colouring of a Graph Generating Graphs Under Constraints Find a Large Independent Set Find an Induced Subgraph in a Random Graph Some Problems Solved Using Graphs A Quiz from the French Journal ``Le Monde 2'' Task Assignment Plan a Tournament Linear Programming Definition Integer Programming In Practice The MixedIntegerLinearProgram Class Variables Infeasible or Unbounded Problems First Applications in Combinatorics Knapsack Matching Flow Generating Constraints and Application Annexes Answers to Exercises First Steps Analysis and Algebra Graphics Computational Domains Finite Fields and Number Theory Polynomials Linear Algebra Polynomial Systems Differential Equations and Recurrences Floating-Point Numbers Non-Linear Equations Numerical Linear Algebra Numerical Integration Enumeration and Combinatorics Graph Theory Linear Programming Bibliography Index