math-utils

The attempt to unify all the math code I wrote in Lisp, which I started to do during my masters degree. Apart from some basic number theory, it mostly deals with implementing various mathematical data structures and some basic algorithms.

The naive idea was to use CLOS to model operations involving different types of math objects, which only worked to some degree. Ultimately, this is not enough and creates problems. Check out SageMath for how a better architecture could look like (but even there you get limitations).

There are some tests available, so the basic functionality required for my continued-fractions project should be in working order.

Pretty (or just understable) output to the REPL (or even exporting to LaTeX) is implemented separately in the math-formatter project.

Functionality

Mathematical data structures

Of course the Common Lisp type number is supported naturally.

Finite fields

For now only those of prime characteristic (no field extensions available).

Fractions

This is mostly to support fractions of polynomials.

Polynomials

While there is some code for multivariate polynomials, it has not been tested extensively and is still missing the division algorithm.

Power/Laurent series

Infinite sequences

Matrices & Linear algebra

Elliptic curves

Only Weierstrass model supported for now

Polynomial factorisation

There is an implementation of the Berlekamp algorithm, but it might still be buggy.

Valuations

only p-adic valuations (and valuations for power series)

There is also some code to transparently compute with bounds for ultrametric valuations and track (see ultrametric-valuation-estimates).

Elementary number theory

• Greatest common divisor
• integer factorisation
• primality tests

Improvements

verbesserte Potenzreihen

• [ ] Praezisionsberuecksichtigung
• [ ] Variablenname

Polynomfaktorisierung

API fuer polynomiale Datenstrukturen

sparse Polynome?

eventuell sind sparse Polynome nuetzlich

multivariate Polynome

monomial orders

Siehe Cox, Little, O’Shea: “Using Algebraic Geometry” und “Ideals, Varieties and Algorithms”

lineare Algebra verbessern

Verzahnung von verschiedenen Datentypen verbessern

Klarere Trennung von Algorithmen zur Berechnung und Benutzerschnittstelle

ist das ueberhaupt moeglich? Wir wollen ja schon bei der Implementation von generischen Funktionen profitieren.

verbesserte Eingabe von Polynomen

infix? sparse Polynome (zur Eingabe) multivariate Polynome

Tasks

define a condition type when taking square roots fails

file:finite-fields.lisp::(error “~A has no square root mod ~A” r p))))

make wider use of definition macro for generic-? methods

file:ultrametric-valuation-estimates.lisp::(def-gm-operation/sym - valuation-estimate (a b)

increase test coverage