konn / computational-algebra Goto Github PK

View Code? Open in Web Editor NEW

92.0 13.0 9.0 119.5 MB

General-Purpose Computer Algebra System as an EDSL in Haskell

Home Page: http://konn.github.io/computational-algebra/

License: BSD 3-Clause "New" or "Revised" License

Haskell 23.41% HTML 75.88% Emacs Lisp 0.02% Shell 0.03% Dockerfile 0.19% Dhall 0.47%

haskell math mathematics computational-algebra groebner-basis ideal polynomial algorithm

computational-algebra's Introduction

Computational Algebra Library

For more detail, please read Official Project Site.

Overview

The computational-algebra is the computational algebra system, implemented as a Embedded Domain Specific Language (EDSL) in Haskell. This library provides many functionality for computational algebra, especially ideal computation such as Groebner basis calculation.

Thanks to Haskell's powerful language features, this library achieves the following goals:

Type-Safety : Haskell's static type system enforces static correctness and prevents you from violating invariants.

Flexibility : With the powerful type-system of Haskell, we can write highly abstract program resulted in easy-to-extend system.

Efficiency : Haskell comes with many aggressive optimization mechanism and parallel computation features, which enables us to write efficient program.

This package currently provides the following functionalities:

Groebner basis calculation w.r.t. arbitrary monomial ordering
- Currently using Buchberger's algorithm with some optimization
- Faugere's F_4 algorithms is experimentally implemented, but currently not as fast as Buchberger's algorithm
Computation in the (multivariate) polynomial ring over arbitarary field and its quotient ring
- Ideal membership problem
- Ideal operations such as intersection, saturation and so on.
- Zero-dimensional ideal operation and conversion via FGLM algorithm
- Variable elimination
Find numeric solutions for polynomial system with real coefficient

Requirements and Installation

Old version of this package is uploaded on Hackage, but it's rather outdated. Most recent version of computational-algebra is developed on GitHub.

It uses the most agressive language features recently implemented in Glasgow Haskell Compiler, so it requires at least GHC 8.0.1 and also it depends on many packages currently not available on Hackage, but you can install it fairly easily with help of The Haskell Tool Stack.

$ curl -sSL https://get.haskellstack.org/ | sh
  # if you haven't install Stack yet
$ git clone https://github.com/konn/computational-algebra
$ cd computational-algebra
$ stack build

In addition, you may need to install GSL and LAPACK (for matrix computation) beforehand. You can install them via Homebrew (OS X), apt-get, or other major package management systems.

Paper

Hiromi Ishii, A Purely Functional Computer Algebra System Embedded in Haskell. Computer Algebra in Scientific Computing, pp. 288-303. 20th International Workshop, CASC 2018, Lille, France, September 17-21, 2018, Proceedings (arXiv).

computational-algebra's People

Contributors

Stargazers

Watchers

Forkers

hangingman hardentoo lemastero silky zzmjohn ldr709 mkummini mxmurw sheaf

computational-algebra's Issues

Haddock failure

cabal haddock yields this error:

dist/build/tmp-21791/Algebra/Algorithms/ZeroDim.hs:319:46:
    parse error on input `-- ^ lex-Groebner basis of the kernel of the given linear map.'

because although Haddock lets you attach documentation to individual function parameters, it does not let you attach it to individual members of a tuple.

Floating-point algorithms?

Apologies if I've missed something, but I couldn't figure out how to use solveM or solve' with floating point coefficients (e.g. Double). Is this possible?

In my situation, the algorithms using Fraction Integer seem much too slow. Something that takes less than a second in Mathematica or Macaulay2 doesn't even terminate after 15 minutes with solveM/solve'.

Here's an example of a system that I've been working with (I cleared the denominators manually, for simplicity)

p = -495 - 5625 * t + 27891 * t^2 - 33372 * t^3 + 13824 * t^4 - 2367 * t^5 + 6345 * u + 25110 * t * u - 170721 * t^2 * u + 230166 * t^3 * u - 110682 * t^4 * u + 15354 * t^5 * u - 18765 * u^2 + 22140 * t * u^2 + 148581 * t^2 * u^2 - 256878 * t^3 * u^2 + 148446 * t^4 * u^2 - 24300 * t^5 * u^2 + 25110 * u^3 - 100440 * t * u^3 + 56970 * t^2 * u^3 + 4860 * t^3 * u^3 - 29160 * t^4 * u^3 + 16740 * t^5 * u^3 - 12960 * u^4 + 51840 * t * u^4 - 27540 * t^2 * u^4 + 33750 * t^3 * u^4 - 21600 * t^4 * u^4 - 8370 * t^5 * u^4 - 3240 * t^2 * u^5 - 25920 * t^3 * u^5 + 25920 * t^4 * u^5

q1 = 52785 + 56943 * t - 4037688 * t^2 + 15883803 * t^3 - 26239221 * t^4 + 20703357 * t^5 - 7724700 * t^6 + 989361 * t^7 - 66015 * u + 487134 * t * u + 27385938 * t^2 * u - 113650722 * t^3 * u + 181819755 * t^4 * u - 135044982 * t^5 * u + 48046662 * t^6 * u - 6530274 * t^7 * u - 2478195 * u^2 + 6294834 * t * u^2 - 111627882 * t^2 * u^2 + 417376962 * t^3 * u^2 - 654613569 * t^4 * u^2 + 478520946 * t^5 * u^2 - 162633582 * t^6 * u^2 + 21861414 * t^7 * u^2 + 13768380 * u^3 - 50360616 * t * u^3 + 247545072 * t^2 * u^3 - 696128256 * t^3 * u^3 + 1052548344 * t^4 * u^3 - 789620400 * t^5 * u^3 + 272718252 * t^6 * u^3 - 36077400 * t^7 * u^3 - 28987470 * u^4 + 118189368 * t * u^4 - 321295572 * t^2 * u^4 + 526662486 * t^3 * u^4 - 679607010 * t^4 * u^4 + 541760724 * t^5 * u^4 - 204607620 * t^6 * u^4 + 26871750 * t^7 * u^4 + 27060480 * u^5 - 113821200 * t * u^5 + 244827360 * t^2 * u^5 - 186998220 * t^3 * u^5 + 124853400 * t^4 * u^5 - 150553080 * t^5 * u^5 + 83446200 * t^6 * u^5 - 9491580 * t^7 * u^5 - 9331200 * u^6 + 39074400 * t * u^6 - 91154160 * t^2 * u^6 + 40979520 * t^3 * u^6 - 5093280 * t^4 * u^6 + 57678480 * t^5 * u^6 - 44634240 * t^6 * u^6 + 3013200 * t^7 * u^6 + 233280 * t * u^7 + 3265920 * t^2 * u^7 + 14929920 * t^3 * u^7 - 22161600 * t^4 * u^7 - 3732480 * t^5 * u^7 + 9331200 * t^6 * u^7

q2 = 919350 - 1206090 * t - 18350955 * t^2 + 58802085 * t^3 - 67806099 * t^4 + 35782614 * t^5 - 8371728 * t^6 + 651591 * t^7 - 5576850 * u + 32915970 * t * u - 20491785 * t^2 * u - 89979930 * t^3 * u + 154823643 * t^4 * u - 98196624 * t^5 * u + 26236818 * t^6 * u - 2518830 * t^7 * u + 9173250 * u^2 - 91559970 * t * u^2 + 183517245 * t^2 * u^2 - 118728180 * t^3 * u^2 - 7137315 * t^4 * u^2 + 55358640 * t^5 * u^2 - 33001290 * t^6 * u^2 + 5753700 * t^7 * u^2 + 1069200 * u^3 + 54276480 * t * u^3 - 129054870 * t^2 * u^3 + 117919800 * t^3 * u^3 - 53146530 * t^4 * u^3 - 19948680 * t^5 * u^3 + 38889720 * t^6 * u^3 - 9797760 * t^7 * u^3 - 11372400 * u^4 + 12733200 * t * u^4 - 9379800 * t^2 * u^4 - 12830400 * t^3 * u^4 + 49223700 * t^4 * u^4 - 15870330 * t^5 * u^4 - 16692480 * t^6 * u^4 + 7690950 * t^7 * u^4 + 4665600 * u^5 - 4665600 * t * u^5 + 21724200 * t^2 * u^5 - 38296800 * t^3 * u^5 + 5297400 * t^4 * u^5 + 1628100 * t^5 * u^5 - 356400 * t^6 * u^5 - 2762100 * t^7 * u^5 - 583200 * t * u^6 - 11664000 * t^2 * u^6 + 23328000 * t^3 * u^6 - 4422600 * t^4 * u^6 + 6536700 * t^5 * u^6 - 2721600 * t^6 * u^6 + 753300 * t^7 * u^6 - 874800 * t^4 * u^7 - 4665600 * t^5 * u^7 + 2332800 * t^6 * u^7

These are polynomials in two variables t, u. Both Mathematica and Macaulay2 can solve the system {p, q1, q2} in less than a second, whereas neither solveM nor solve' can finish under 15 minutes.

In this case, I'm looking for the real solutions with t,u in the unit interval, which are:

t = 0.376357, u = 0.106547
t = 0.886678, u = 0.626615

I also tried to use Fraction Int, but a lack of instances prevented that from working.

doesn't build on 8.2

Hello!
this lib sadly doesn't seem to build on ghc 8.2
in some cases this may be because of dependencies. If theres any way I or other hackage trustees can help make it happen do let me or other know via the tools / issue tracker over at https://github.com/haskell-infra/hackage-trustees/

many thanks!
-Carter

newtype Monomial ( n :: Nat ) = Monomial ( Array# Word )

or, avoiding all indirections entirely:

data family Monomial ( n :: Nat ) :: TYPE ( 'TupleRep ( Replicate n WordRep ) )
newtype instance Monomial 0 = M0 (# #)
newtype instance Monomial 1 = M1 (# Word# #)
newtype instance Monomial 2 = M2 (# Word#, Word# #)
newtype instance Monomial 3 = M3 (# Word#, Word#, Word# #)
newtype instance Monomial 4 = M4 (# Word#, Word#, Word#, Word# #)
...

I'm also wondering if a Map is the best data-structure to use to represent polynomials, but I suppose that's best left to a separate ticket.