#Current Challenges
      in the
      #Open Source
      #Computer Algebra Software
      My name is
      #Christian Eder
      I'm from the
      #University of Kaiserslautern

      #DFG Collaborative
      #Research Center
      #TRR 195
      Kaiserslautern, Aachen, Saarbrücken
      + many others

      Methods from Computer Algebra
      are nowadays firmly established
      in the toolbox of the pure

      Fruitful interactions between
      Algebraic Geometry,
      Computer Algebra,
      Group & Representation Theory,
      Number Theory and
      Polyhedral Geometry

      Our approach

      Open Source
      Computer Algebra

      group & representation theory,
      general purpose high level
      interpreted language

      *GAP* - Projective Special Linear Groups
        gap> grp:=PSL(5,3);;
        gap> a:=PseudoRandom(grp);;
        gap> b:=PseudoRandom(grp);;
        gap> Size( Group(a,b) );
        237783237120 // 10 msec on this machine

      polynomial computations in
      algebraic geometry,
      commutative algebra &
      singularity theory

      *SINGULAR* -
      Parametrization of rational curves
        > LIB"paraplanecurves.lib";
        > ring r = 0,(x,y,z),dp;
        > poly f = x5+10x4y+20x3y2+130x2y3-20xy4+20y5
        . -2x4z-40x3yz-150x2y2z-90xy3z
        . -40y4z+x3z2+30x2yz2+110xy2z2+20y3z2;
        > genus(f); // may require blow-ups
        > paraPlaneCurve(f); // normalization, integral bases


      convex polytopes, polyhedral fans,
      simplicial complexes, related objects
      from combinatorics & geometry

      *polymake* - Normal fans (via SINGULAR)
        > LIB"polymake.so"; // credits for polymake
        > ring r=0,(x,y),dp;
        > poly f=x3+y3+1; // last SINGULAR-only statement
        > polytope p = newtonPolytope(f);
        > fan F = normalFan(p);
        > F;
        RAYS:       MAXIMAL CONES:
        -1 -1 #0    {0 1} #Dimension 2
         0  1 #1    {0 2}
         1  0 #2    {1 2}


      number theory software, computations
      in & with number fields and generic
      finitely presented rings
      created within SPP-1489

			*ANTIC* - Class Groups & Extended GCDs
        > Qx, x = PolynomialRing(QQ, "x")
        > f = x^6+141*x^5-141*x^4+141*x^3-141*x^2+141*x-141
        > K, a = NumberField(f);
        > M = lll(maximal_order(K));
        > class_group(M)
        > Kt, t = PolynomialRing(K, "t")
        > g = sum([K(rand(M, 100))*t^i for i=1:20])
        > h = sum([K(rand(M, 100))*t^i for i=1:20])
        > @time gc, a, b = gcdx(g, h);



      Design & development
      of a CAS in general
      driven by intended


      Mumford (1980):
      Can a computer classify all surfaces of
      general type with pg = 0?

      Let X be a minimal surface
      of general type with pg=0
      such that (KX)2 = 1
      → numerical *Godeaux surfaces*
      X Godeaux surface
      ⇒ H1(X,ℤ) is cyclic of
      order at most 5
      Constructions have been
      given for each such order.

      There is precisely one irreducible
      family of surfaces for each order.

      Experimental approach to
      solve this conjecture:
      1. Construct random points
      1. in moduli spaces.
      2. Study related geometry
      2. via CAS.

      Requirements for this approach:
      1. Computational Algebraic Geometry
      2. Topology
      3. Group Theory

      Joint project by
      Wolfram Decker & Isabel Stenger
      Frank-Olaf Schreyer
      in collaboration with Miles Reid

      Why is this computationally hard
      from the very beginning?

        > Rextension;
        // characteristic : 0
        // 1 parameter    : a
        // minpoly        :
        // number of vars : 12


      #High Energy Phsyics
      joint work with
      Pierpaolo Mastrolia and Tiziano Peraro



      For example,
        > ring r=(0,p11,p12,p22,e34,m1,m2,m3),(x1,x2,x3,x4),dp;
        > poly D1=2*x3*x4*e34+x1*(p11*x1+p12*x2)
        . +(x1*p12+p22*x2)*x2-m1;
        > poly D2=-m2+2*x3*x4*e34-2*p11*x1+p11+x1*(p11*x1+p12*x2)
        . +(x1*p12+p22*x2)*x2-2*p12*x2;
        > poly D3=2*x3*x4*e34+2*x1*p12-m3+x1*(p11*x1+p12*x2)+p22
        . +(x1*p12+p22*x2)*x2+2*p22*x2;
        > ideal I = D1, D2, D3;
        > ideal GI = groebner(I);

      #Challenge #1
      Efficiency of Fundamental Algorithms

      Low level Implementations
      *Gröbner Bases* & *Standard Bases*
      *Syzygies* & *Free Resolutions*
      *Polynomial Factorization*

      *F4 Algorithm* for SINGULAR
      based on special-purpose
      linear algebra library *GBLA*
      joint work with
      Jean-Charles Faugère
      & the PolSys team








      High level Implementations

      *Primary decomposition*
      (de Jong, Greuel-Laplagne-Seelisch)
      analyzing *Singularities*
      (Hamburger-Noether expansions, blow-ups,
       resolution of singularities, etc.)

      Other Packages


      Symbolic calculations with generic
      character tables of groups
      of Lie type & more
      Constructive homological algebra
      Category theory part for homalg

      Fast library for number theory
      (Hart-Johansson-et al)

      Algebraic number theory,
      recursive generic rings

      Class groups, orders in number fields,
      lattice enumeration, sparse linear algebra

      Algorithmic tropical
      intersection theory

      even more packages
      & many more

      Challenge #2

      Thread Level
      (fine grain)




      Many fundamental algorithms
      are sequential in nature

      Process Level
      (coarse grain)

      General scheme for
      *modular methods*
      for algorithms
      over the rationals.

      e.g. GBs over the rationals
      (Arnold, Idrees-Pfister-Steidel,
      (& many more)

      or GBs over algebraic number fields


      Or try to find new approaches

      *Local-to-global Approach* to Normalization
      1. Stratify the singular locus.
      2. Compute local contribution to the
      2. normalization at each stratum.
      3. Put the local contributions back together.

      How to combine different
      levels of parallelization
      in a *convenient* way?
      Experts? Non-experts?

      x86 CPUs are not the
      whole picture

      #Cluster of 256 Raspberry Pis
      (src: https://www.raspberrypi.org/magpi/seemore/)

      massively-parallel multicore processors,
      on-chip / discrete GPUs, ARM chips,
      heterogenous computation (OpenCL),
      distributed computation on our
      phones & tablets, ...

      #Challenge #3
      Make Abstract Concepts of Pure
      Mathematicians Constructive

      *Category Theory*
      influenced object-oriented
      & functional programming

      #Wormholes in mathematics
      (license: GNU-FDL, made by Panzi)

      1. Translate problems in entirely different context.
      2. Switch to more efficient data structures.
      3. Get reduced computational complexity.

      #Challenge #4
      A Convenient Hierarchy of Languages



      What is  ?

      > high-level dynamic programming
      > language, also functional
      > interactive shell: read-eval-print loop (REPL)
      > just-in-time compilation
      > good performance
      > can call Python & C functions
      > built-in package manager
      > designed for parallel &
      > distributed computing

      #How will SINGULAR use Julia?
      Still *experimental*
        julia> f(x) = 2x+1; g(x,y) = y+2f(x)
        julia> println("I think", g(1,1), "is prime.")
        I think 7 is prime.
        julia> using Singular

      #Challenge #5
      Data Bases

      Collect results of extensive
      & time-consuming calculations
      in *databases*.

      Oh, and don't forget to make
      them *publicly* available.

      #Well, backups would
      #be great, too
      nous venons malheureusement de perdre 2 disques
      de données sur 10, simultanément, sur la machine xxx,
      qui était en RAID 5.
      A priori cela implique que *toutes les données sont perdues*.

      #Challenge #6
      Development Model

      A single

      Conerstones are *submodules*
      ⇒ OSCAR references only a
      single commit of a submodule

      Phase 1
      (first 1/2 year)

      0. Repository is private (oh no!)
      1. All can push to OSCAR repository
      2. CI only for compile success testing
      3. Minimal tests
      4. Set feature flags for broken parts

      Phase 2

      0. Make repository public :)
      1. Collaboration for everybody only
      1. via tested pull requests
      2. CI tests via Jenkins
      3. Code review in pull requests
      4. One main development branch,
      4. branches for releases

      #Challenge #7
      Easy Access

      Horizon 2020 European Research
      Infrastructure project
      Aim: Provide intuitive user interfaces.


      Give non-experts
      to click on.



      Mohamed Barakat, Janko Böhm,
      Wolfram Decker, Claus Fieker,
      Sebastian Gutsche, Gert-Martin Greuel,
      Bill Hart, Tommy Hofmann,
      Gunter Malle, Gerhard Pfister,
      Lukas Ristau, Mathias Schulze,
      Andreas Steenpaß, Isabel Stenger
      & many more

      One Last
      Commercial Break

      #ISSAC 2017
      The 42nd International Symposium
      on Symbolic and Algebraic Computation
      University of Kaiserslautern, Gemany,
      *July 25 - 28, 2017*

      #PASCO 2017
      International Workshop on Parallel
      Symbolic Computation
      University of Kaiserslautern, Gemany,
      *July 23 - 24, 2017*

      Thank you
      for your