#Current Challenges
      in the
      #Development
      of
      #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
      mathematician.



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

      Our approach

      #OSCAR
      Open Source
      Computer Algebra
      Resource

      Four
      cornerstones
      
      #GAP
      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

      #SINGULAR
      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
        0
        > paraPlaneCurve(f); // normalization, integral bases

      

      #polymake
      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}

      

      #ANTIC
      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
      applications

      Mathematical
      applications

      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.

      Conjecture:
      .
      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
      (Kaiserslautern)
      Frank-Olaf Schreyer
      (Saarbrücken)
      .
      in collaboration with Miles Reid
      (Warwick)

      Why is this computationally hard
      from the very beginning?

      .
        > Rextension;
        // characteristic : 0
        // 1 parameter    : a
        // minpoly        :
        (24873879473832817299558394474990433025260537858429700*a^8
        +412197480758832021377448558823165698794277118212212070*a^7
        +625366891611244986389942014312773193649951168354090190*a^6
        -436561073546512334083477547357856090524552855592558795*a^5
        -914947642504230095779800456657440020138074539186145912*a^4
        -2227325279423247966617649640155997715235288113299887954*a^3
        +2312070077580715288467637707530192772778088469836344950*a^2
        +1366053134215201364075122803745127996518986576734818612*a
        -1156759915557562158859054495379551857229358735237021536)
        // number of vars : 12

      "Non-mathematical"
      applications

      #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*
      (Gianni-Trager-Zacharias,
       Shimoyama-Yokoyama,
       Eisenbud-Huneke-Vasconcelos)
      .
      *Normalization*
      (de Jong, Greuel-Laplagne-Seelisch)
      .
      analyzing *Singularities*
      (Hamburger-Noether expansions, blow-ups,
       resolution of singularities, etc.)

      Other Packages

      


      *CHEVIE*
      Symbolic calculations with generic
      character tables of groups
      of Lie type & more
      (Geck-Hiß-Lübeck-Malle-Michel-Pfeiffer)
      
      *homalg*
      Constructive homological algebra
      (Barakat-Gutsche-Lange-Hegemann-Posur)
      .
      *CAP*
      Category theory part for homalg
      (Gutsche-Posur)


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

      *NEMO*
      Algebraic number theory,
      recursive generic rings
      (Fieker-Hart-Hofmann-Johansson-Motsak)

      *HECKE*
      Class groups, orders in number fields,
      lattice enumeration, sparse linear algebra
      (Fieker-Hofmann)


      *A-TINT*
      Algorithmic tropical
      intersection theory
      (Hampe)


      even more packages
      .
      *4ti2*
      *cddlib*
      *Gfan*
      *normaliz*
      & many more

      Challenge #2
      Parallelization

      Thread Level
      (fine grain)

      

      

      

      *Problem*
      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
      (Boku-Decker-Fieker-Steenpaß)

      

      Or try to find new approaches

      *Local-to-global Approach* to Normalization
      (Böhm-Decker-Laplagne-Pfister-Steenpaß-Steidel)
      .
      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?

      *Btw:*
      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

      

      


      Who 
      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*
      https://github.com/wbhart/Singular.jl
      .
        julia
        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
      .
      Bonjour,
      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
      OSCAR
      repository

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

      Development
      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

      Development
      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


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


      Possible
      Solution?

      Give non-experts
      *buttons*
      to click on.

      

      

      #Credits
      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
      attention

      Questions?
      Remarks?