Category Archives: Computer Math

Compiling Giac in Windows (Cygwin)

I tried many times to compile giac for windows. Giac is a computer algebra system that has the advantage of being very flexibly adaptable to many operating system (if I remember correctly these include: linux, macintosh, WinCE, Android, windows). I believe that the developer(s) (mainly Bernard Parisse) mostly develop for linux. But they made sure that this can be compiled in many other operating systems. They even provided makefiles adapted for different operating systems. As with many other software that claims universal compilability, one needs to still work to get this compiled in an operating system foreign to the developers.

In the past my compilation failed because of some dependencies that I did not understood or because of some flags that I did not set. So after many years, while I was idle in some math conference, I decided to write to the developers and ask their help. Initially I wanted to join their forum, which would allow easier communication between developers and users. It took a while for me to get into their forum. For some reasons, many computer algebra systems seem to have discussion forums that are dormant or very difficult to register. I do remember the same problem when I wanted to register to the Singular forum. After successfully joining the forum, it somehow exhausted me so I did not pursue the question of compiling giac in windows. This was not a wise decision, still after a year I saw the need to compile giac. Switching to linux was a last resort option for me. My developments are so deeply windows rooted that I had to do everything and port to linux and the workload could be much more than trying to find a way to compile giac.

After posting the question in their forum, I was surprised how helpful Bernard was in guiding me. I had three steps in mind if I wanted to have the giac library working in windows:

  1. successfully compile in Cygwin
  2. successfully compile in Mingw32
  3. Successfully compile a library for Visual Studio (2008)

I am glad to announce that I am satisfied with: compiling for cygwin and compiling with mingw32. My next and final goal is to try it in visual studio (which belongs to a separate blog.). I promised Bernard I will document this in a blog because there seems to be a lack of information for early developers using giac (the forum and some old site writes about it, but giac deserves much much more).

To start the walkthrough let me first write that many things (unknown to many people) use giac. Among many others softwares and hardwares the following depends on giac: HP Prime Calculator, TI NSpire calculator, Geogebra. I really believe this boils down to its flexibility playing well in different operating system and environments and its minimal system requirement (which I don’t know what is, but the fact that low spec calculators can work with it is amazing already).

Let us now start with the walkthrough for cygwin. Warning: since this is personalized some filenames in my tutorial uses my initial name (jose) but you can use whatever name you want.

  1.  Download the latest giac source code from  https://www-fourier.ujf-grenoble.fr/~parisse/giac/giac_stable.tgz
  2. Decompress the archive and go to its root directory and run ./configure. This will search installed components and and adjust the config.h in src folder accordingly (make sure you have installed at least gmp in cygwin)
  3. Compare the created config.h with config.h.win64 (in src directory) and check if there is anything wrong. For instance, in my case I specifically did not want to have FLTK (even though I had it already installed in cygwin, as this was only xcas related). So I did the following additional changes:
    • I removed all the FLTK options in config.h
    • I removed all NTL and INTL from the options

    Here, by “remove”, I mean I commented them out instead of trying to use #define to 0 because this wouldn’t work (for me). Giac checks predefinitions by #ifdef and not with #if

  4. In the source directory copy Makefile.win64 to Makefile.jose and edit Makefile.jose
  5. In Makefile.jose:
    • remove the capital letter objs in “OBJS = ” (they are related to GUI application, xcas, etc. which is not what I wanted to build. I want to build giac independent on unnecessary libraries)
    • remove Tmpl…, TmpFLG… and other capital letter obj files from “GIACOBJS=”
    • remove: -lintl.dll, -lintl, -lntl, -ftlk** (anything fltk related), libreadline.a, libhistory.a, libncurses.a, -lgsl, -lgslcblas, -llapack (I did not want to build with blas and lapack).
    • I left mpfr (and if you want you can put in libpari, but that will be discussed later) because I found multiprecision floating point kind of necessary. Do not remove gmp! (and if you want leave ntl but I did not experimented with that)
  6. Execute
    make -f Makefile.jose giac.dll
    in src directory

After you have done all this, you can execute a minimal program (Bernard provided me with a minimal program that try giac.dll. Thank you Bernard if you are reading this!). Namely save the following code as jose.cc (I saved in the src directory, but you don’t need to be as dirty as me!):

#include <giac/config.h>
#include <giac/giac.h>

using namespace std;
using namespace giac;

gen pgcd(gen a,gen b){
  gen q,r;
  for (;b!=0;){
    r=irem(a,b,q);
    a=b;
    b=r;
  }


  return a;
}

int main(){
  cout << "Enter 2 integers ";
  gen a,b;
  cin >> a >> b;
  cout << pgcd(a,b) << endl;
  return 0;
}

Now in the same directory (asuming obj files are also there) run:

To compile
g++ -g -I. -DWIN32 -DHAVE_CONFIG_H -DIN_GIAC -DUSE_OPENGL32 -fno-strict-aliasing -DGIAC_GENERIC_CONSTANTS -c jose.cc

To link an create an executable called jose.exe
g++ -g -I. -DWIN32 -DHAVE_CONFIG_H -DIN_GIAC -DUSE_OPENGL32 -fno-strict-aliasing -DGIAC_GENERIC_CONSTANTS gl2ps.o jose.o -o jose giac.dll -mwindows -L/usr/local/lib /usr/lib/libreadline.a /usr/lib/libhistory.a /usr/lib/libncurses.a -lole32 -luuid -lcomctl32 -lwsock32 -lglu32 -lopengl32 -ldmoguids -lgsl -lgslcblas -lrt -lpthread -ldl -lmpfr -lgmp -lz

If things went well you can run the program which computes the gcd of two numbers. Here is the output:

E:\cygwin\usr\src\giac\giac-1.2.3\src\bin\Release>jose
Enter 2 integers 2 3
1

In a next blog I will explain how to compile it independent of cygwin (mingw32). I also will discuss some methods to optimize the output by dynamically linking to standard libraries.

Animating in Mathematica

M. gave us a lecture on how $S_4$ can be regarded as rigid transformation (rotations about the origin) of a cube centered at the origin. This was not straightforward for me to visualize. So ,after a long contemplation what to use: OpenGL/C++, Povray+Blender, Mathematica and its very useful animation features, I ended up deciding to use Mathematica. I had an intuition that Mathematica, albeit not being perfect in animation and visualization like Blender and Povray will provide for a very fast result (which at the moment was a priority for me). To visualize this you can use the following code:

g=Graphics3D[{Opacity[0.3], Cuboid[{-5, -5, -5}, {5, 5, 5}], 
  Opacity[1.0], Thick, Green, Line[{{-5, -5, -5}, {5, 5, 5}}], 
  Line[{{5, -5, -5}, {-5, 5, 5}}], Line[{{-5, 5, -5}, {5, -5, 5}}], 
  Line[{{-5, -5, 5}, {5, 5, -5}}], Black, 
  Text[Style[1, Large, Bold, Red], {5, 5, 5}],
  Text[Style[2, Large, Bold, Red], {5, -5, 5}],
  Text[Style[3, Large, Bold, Red], {-5, 5, 5}],
  Text[Style[4, Large, Bold, Red], {-5, -5, 5}]},Boxed->False,PlotRange->{{-9,9},{-9,9},{-9,9}}];
Animate[MapAt[Rotate[#, t,{0,5,5},{0,0,0}]&,g,{1}],{t,0,Pi},
  AnimationRunning->False,AnimationRepetitions->1,AnimationDirection->ForwardBackward,FrameLabel->"Transposition(1,3)"]
Animate[MapAt[Rotate[#,t,{5,5,5},{0,0,0}]&,g,{1}],{t,0,2Pi/3},
  AnimationRunning->False,AnimationRepetitions->1,AnimationDirection->ForwardBackward,FrameLabel->"3-Cycle (2,3,4)"]
Animate[MapAt[Rotate[#,t,{0,0,1},{0,0,0}]&,g,{1}],{t,0,Pi/2},
  AnimationRunning->False,AnimationRepetitions->1,AnimationDirection->ForwardBackward,FrameLabel->"4-Cycle (1,3,4,2)"]
Animate[MapAt[Rotate[#,t,{0,0,1},{0,0,0}]&,g,{1}],{t,0,Pi},
  AnimationRunning->False,AnimationRepetitions->1,AnimationDirection->ForwardBackward,FrameLabel->"2 Transpositions (1,4)(2,3)"]

Yes combining the Animate in one single panel was rather a pain as I did not know how to change variables (axis and angle of rotation) all in one panel (I wasn’t able to do it with Buttons and Dynamic in Mathematica).

If you do not have Mathematica, you can still download the animation file here. Now I am proud to claim that I did a Mathematica animation on my own: Time from 0-knowledge to one animation = Roughly 1 hour. If this was Blender+Povray, although I have experience in working with them, I would still need much more time to model, texture and finally generate the animation. So my conclusion is: although the animations and features of Mathematica has many things left to be desired, it is probably the best choice if you want to animate a few mathematical object very fast on the fly. The 1hr work I invested, is now a 5min. work for any other remainder animation I want to make in Mathematica. If the animation I want to do would require much more time than this, e.g. complicated interactions with buttons, phong and radiosity etc., I would probably look at other options as well.

To save an avi you may use something like the following (notice: I have hidden sliders and panel for a better look of the video).


Export["C:/temp/output1.avi",
Manipulate[MapAt[Rotate[#, t,{0,5,5},{0,0,0}]&,g,{1}],{t,0,Pi,
AnimationRunning->True,AnimationDirection->ForwardBackward,AnimationRepetitions->1,Paneled->False,ControlType->None},
FrameLabel->"Transposition(1,3)"]
]

This results in a very poor video compression (quality of videos were OK, but for 4sec. I got 35Mb of video). But that is easily remedied by using Handbrake (I do this if I don’t have too much time to play around more complicated tools) or VirtualDub (which I only use if I have a lot of time to invest.. which is sadly less often the case). I combined the four different videos showing a permutation from each conjugacy class of $S_4$. Here is the final video after compression (also a link was given earlier for you to download the video in case you do not have HTML5 support in your browser):

Mathematica and me

$
\newcommand\R{\mathbb{R}}
$
The last time I think I was serious with Mathematica was 2001? or maybe a few years earlier. I really cannot remember. But I left it and always looked at Maple for enlightenment (where I was/am not still good at). In the past when I looked at Mathematica I thought of it as a Maple similar and probably any amateur would still believe this to be. Both very clumsy to work with. Now, 2016, they differ so much and have advanced so much. One is good at one thing, the other at another. But this is not a debate which is better. This is a “tutorial” what you can do a little good with one. Today Mathematica won my heart (another day it could be Maple). Because the topic “Cylindrical Algebraic Decomposition” (which we in the real world, i.e. real algebraic geometry world, just simply call “cylindrical decomposition”) expresses the strength of Mathematica.

A Mathematica code is a bit different from a C++ code (or even Maple) that I am more used to. So let me list down some things I (think I) learned during the coarse of a few days looking at one or two codes:

  • f @ something means apply f to x
  • f @@ List[...] means change List to f
  • f @@@ List[List[...]] means List[f[...]]

The first problem that I had is the following: Given an real algebraic set defined by a polynomial function $f:\R^m\rightarrow \R$ , find the number of connected component of the complement of this set. Also find an “algorithm” that can tell if two elements in $\R^m$ belong in the same connected component.

For the sake of argument I took $m=2$ and variables to be $x$ and $y$. Then I wanted to find the connected components of all those $(x,y)$ for which $f(x,y)\neq 0$. To this I copied and modified a code from a mathematica stackexchange post and the modified code looks like this

Coco[eqns_, xrange_: {x, -1, 1}, yrange_: {y, -1, 1}, 
  plotit_: False] := 
 Module[{decomp, connected, regconn}, 
  regconn = 
   Resolve@Exists[{x, y}, (x | y) \[Element] Reals, 
      RegionMember[
       RegionIntersection[ImplicitRegion[#1, {x, y}], 
        RegionBoundary@ImplicitRegion[#2, {x, y}]], {x, y}]] &;
  decomp = 
   List @@ BooleanMinimize@CylindricalDecomposition[eqns, {x, y}];
  connected = 
   Or @@@ ConnectedComponents@
     Graph[decomp, 
      UndirectedEdge @@@ 
       Select[Subsets[decomp, {2}], 
        regconn @@ # || regconn @@ Reverse@# &]];
  Print["number of connected components: ", Length@connected];
  If[plotit,Print[
    (Quiet@
         RegionPlot[#, xrange, yrange, 
          PlotPoints -> 100] & /@ {decomp, connected})~
     Join~{FullSimplify[connected, (x | y) \[Element] Reals]}]]; 
  Return[connected]]

As you can see the code just simplifies the regions defined by cylindrical algebraic decomposition using disjunctive normal form and then finds the regions of intersection by identifying each region as a vertex of a graph and then connecting the vertices if they have common intersections. Then Mathematicas (quit powerful) graph theory package can figure out the connected components of the graph and thus identify exactly the connected components of the Zariski open set defined by the complement of the hypersurface. This, I think, is an overkill. You really need not convert everything into a graph and use Mathematica’s connected component procedure for graph. You just need to use pigeon-hole principal by placing each region in a set containers and iteratively by order fill the set containers depending on common intersection of region or make a new container if there is no existing set container having region with common intersection. Since I was/am a lazy animal and the procedure was fast enough for my purpose, I left it as it was.

I tested this on a curve for which I knew how many connected components it’s complement have, namely the curve $y^2=x(x-1)(x-2)(x-3)(x-4)$ the plotof which looks like this:
curve_4_coco

After applying the Coco on the curve by typing (the three other parameters in Coco are optional, they are only used to plot the regions)

connected = Coco[y^2 != x(x-1)(x-2)(x-3)(x-4),{x,0,5},{y,-10,10},True];

I get the picture for the cylindrical algebraic decompositions

the picture of the different components

the number of components and the actual regions given (click to see in full glory)

The counting of component for this function, without plotting, took around 6.7 seconds in my not-so-fast laptop. Understandably, most of the time was sucked by the plotting. The plotting does not concern me a lot so I am happy with this. I think it can even be made faster (I predict, with correct coding and optimization you can squeeze it to 2 seconds).

Hopefully, in a future post I will show how this is done (with less pictures) when the hypersurface lies in a space with dimension greater than two (i.e. $m>2$).