(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 7.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[     77369,       2360]
NotebookOptionsPosition[     71266,       2149]
NotebookOutlinePosition[     71989,       2177]
CellTagsIndexPosition[     71861,       2171]
WindowFrame->Normal*)

(* Beginning of Notebook Content *)
Notebook[{
Cell["\<\
A GCD based Hermite Normal Form algorithm, stabilized in the Chou Collins  or \
Lenstra Lenstra Lov\[AAcute]sz manner.\
\>", "Title"],

Cell[TextData[{
 "We present a rather simple code to illustrate that the principles that \
prevent coefficient explosion in the LLL algorithm also suffice in a naive \
GCD based Hermite Normal Form algorithm.This should not come as a surprise, \
because Chou and Collins have already shown this long ago, at least for an \
input matrix of full rank. \nQuery: Does anyone know of a more recent \
treatment, not restricted to input of full rank?\nA GCD based operation \
amounts to a sequence of ordinary row operations. We know from LLL that one \
does not need to length reduce everything all the time. From my analysis of \
an extended LLL algorithm it is clear that it suffices to do the following. \
Each time before a new row is allowed to enter the fray one must bring the \
matrix above it into (lower triangular) Hermite Normal Form. So one should \
not be satisfied with a lower triangular form.  To avoid coefficient \
explosion one should go all the way to Hermite Normal Form. One can prove an \
(extended) LLL like estimate for the given code in the manner of my analysis \
of ",
 StyleBox["extendedlll",
  FontWeight->"Bold"],
 ". Thus the analysis of Chou and Collins is very much related to that of LLL \
and ",
 StyleBox["extendedlll",
  FontWeight->"Bold"],
 ". In fact Chou and Collins covered the case that corresponds with the \
extended hnf call ",
 StyleBox["hnf[matrix,symbol]",
  FontWeight->"Bold"],
 " as introduced below. They did not cover the case of the call ",
 StyleBox["hnf[matrix]",
  FontWeight->"Bold"],
 ", which is faster and allows dependent vectors. (They added an identity \
matrix to make the vectors independent).  Our main point is that it helps to \
think of their Hermite Normal Form algorithm as belonging to the same family \
as the LLL algorithm, or vice versa. \nWe also like to stress that our simple \
code describes an algorithm that often outperforms the algorithm of P. \
Domich, R. Kannan and L. Trotter, as implemented by Victor Shoup in NTL. \
Recall that their algorithm counters coefficient explosion by using modular \
arithmetic. When no small multiple of the pivots exists (or when none is \
known), it seems much better to prevent the explosion than to try and cure it \
by computing modulo some large number.\nRecall that one sees terrible \
explosions when the intermediate stabilizing steps are left out. \nWilberd \
van der Kallen ,   November 2003 but converted to ",
 StyleBox["Mathematica",
  FontSlant->"Italic"],
 " 7."
}], "Text",
 CellChangeTimes->{{3.451454503822357*^9, 3.451454537876588*^9}},
 FontSize->16],

Cell[CellGroupData[{

Cell["The hnf code", "Section"],

Cell[BoxData[{
 RowBox[{
  RowBox[{"SetAttributes", "[", 
   RowBox[{"hnf", ",", "HoldAll"}], "]"}], "\[IndentingNewLine]"}], "\n", 
 RowBox[{
  RowBox[{
   RowBox[{"hnf", "::", "usage"}], ":=", 
   "\"\<{newmatrix,rank}=hnf[mat] gives a lower triangular Hermite Normal \
Form of the integral matrix mat, together with its rank.\\n\n\
{newmatrix,rank}=hnf[matrix,symbol] also assigns to symbol the matrix trans \
so that trans.mat=newmatrix.\>\""}], "\[IndentingNewLine]"}], "\n", 
 RowBox[{
  RowBox[{"hnf", "[", 
   RowBox[{"bb_", ",", 
    RowBox[{"uu_:", "False"}]}], "]"}], ":=", "\[IndentingNewLine]", 
  RowBox[{"Module", "[", "\[IndentingNewLine]", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"u", ",", 
      RowBox[{"m", "=", 
       RowBox[{"Length", "[", "bb", "]"}]}], ",", 
      RowBox[{"n", "=", 
       RowBox[{"Length", "[", 
        RowBox[{"bb", "[", 
         RowBox[{"[", "1", "]"}], "]"}], "]"}]}], ",", "i", ",", "j", ",", 
      "l", ",", "pp", ",", "bb0", ",", 
      RowBox[{"rank", "=", "0"}], ",", 
      RowBox[{"dimker", "=", "0"}], ",", 
      RowBox[{"k", "=", "1"}], ",", 
      RowBox[{"maxk", "=", "0"}], ",", "ans"}], "}"}], "\[IndentingNewLine]", 
    ",", "\[IndentingNewLine]", 
    RowBox[{
     RowBox[{"pp", "=", 
      RowBox[{"0", " ", 
       RowBox[{"Range", "[", "m", "]"}]}]}], ";", 
     RowBox[{"(*", " ", 
      RowBox[{
      "initialize", " ", "as", " ", "a", " ", "row", " ", "of", " ", 
       "zeroes"}], " ", "*)"}], "\[IndentingNewLine]", 
     RowBox[{"If", "[", 
      RowBox[{
       RowBox[{"uu", "=!=", "False"}], "\[IndentingNewLine]", ",", 
       RowBox[{"(*", " ", 
        RowBox[{
         RowBox[{
         "If", " ", "the", " ", "transformation", " ", "is", " ", 
          "requested"}], ",", " ", "\[IndentingNewLine]", 
         RowBox[{
         "put", " ", "an", " ", "identity", " ", "matrix", " ", "in", " ", 
          "front"}], ",", " ", 
         RowBox[{
         "to", " ", "keep", " ", "track", " ", "of", " ", "the", " ", 
          RowBox[{"transformation", "."}]}]}], " ", "*)"}], 
       "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"bb0", "=", 
         RowBox[{"Transpose", "[", 
          RowBox[{"Join", "[", 
           RowBox[{
            RowBox[{"IdentityMatrix", "[", "m", "]"}], ",", 
            RowBox[{"Transpose", "[", "bb", "]"}]}], "]"}], "]"}]}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"n", "=", 
         RowBox[{"n", "+", "m"}]}]}], "\[IndentingNewLine]", ",", 
       "\[IndentingNewLine]", 
       RowBox[{"bb0", "=", "bb"}]}], "\[IndentingNewLine]", "]"}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"For", "[", 
      RowBox[{
       RowBox[{"i", "=", "1"}], ",", 
       RowBox[{"i", "\[LessEqual]", "m"}], ",", 
       RowBox[{"i", "++"}], "\[IndentingNewLine]", ",", 
       RowBox[{"(*", " ", 
        RowBox[{
        "Record", " ", "how", " ", "far", " ", "row", " ", "i", " ", "sticks",
          " ", 
         RowBox[{"out", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"j", "=", "n"}], ";", "\[IndentingNewLine]", 
        RowBox[{"While", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"(", 
            RowBox[{"j", ">", "0"}], ")"}], "&&", 
           RowBox[{"(", 
            RowBox[{
             RowBox[{"bb0", "[", 
              RowBox[{"[", 
               RowBox[{"i", ",", "j"}], "]"}], "]"}], "\[Equal]", "0"}], 
            ")"}]}], ",", 
          RowBox[{"j", "--"}]}], "]"}], ";", "\[IndentingNewLine]", 
        RowBox[{
         RowBox[{"pp", "[", 
          RowBox[{"[", "i", "]"}], "]"}], "=", "j"}], ";"}]}], 
      "\[IndentingNewLine]", "]"}], ";", "\[IndentingNewLine]", 
     RowBox[{"While", "[", 
      RowBox[{
       RowBox[{"k", "\[LessEqual]", "m"}], "\[IndentingNewLine]", ",", 
       "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"maxk", "=", "k"}], ";", 
        RowBox[{"(*", " ", 
         RowBox[{
         "number", " ", "of", " ", "new", " ", "row", " ", "that", " ", "is", 
          " ", "to", " ", "be", " ", "processed"}], " ", "*)"}], 
        "\[IndentingNewLine]", 
        RowBox[{"While", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"(", 
            RowBox[{"k", ">", 
             RowBox[{"dimker", "+", "1"}]}], ")"}], "&&", 
           RowBox[{"(", 
            RowBox[{
             RowBox[{"pp", "[", 
              RowBox[{"[", "k", "]"}], "]"}], "\[LessEqual]", 
             RowBox[{"pp", "[", 
              RowBox[{"[", 
               RowBox[{"k", "-", "1"}], "]"}], "]"}]}], ")"}]}], 
          "\[IndentingNewLine]", ",", "\[IndentingNewLine]", 
          RowBox[{
           RowBox[{"swap", "[", 
            RowBox[{"k", ",", "bb0", ",", "pp"}], "]"}], ";", 
           RowBox[{"(*", " ", 
            RowBox[{"uses", " ", "extended", " ", "Euclid"}], " ", "*)"}], 
           "\[IndentingNewLine]", 
           RowBox[{"k", "--"}], ";"}]}], "\[IndentingNewLine]", "]"}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"If", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"pp", "[", 
            RowBox[{"[", "k", "]"}], "]"}], "\[Equal]", "0"}], ",", 
          RowBox[{"dimker", "++"}], ",", 
          RowBox[{"rank", "++"}]}], "]"}], ";", "\[IndentingNewLine]", 
        RowBox[{"For", "[", 
         RowBox[{"Null", ",", 
          RowBox[{"k", "\[LessEqual]", "maxk"}], ",", 
          RowBox[{"k", "++"}], "\[IndentingNewLine]", ",", 
          RowBox[{"(*", " ", 
           RowBox[{
            RowBox[{"Reduce", " ", "the", " ", "columns"}], ",", " ", 
            RowBox[{"as", " ", "required", " ", "by", " ", 
             RowBox[{"Hermite", "."}]}]}], " ", "*)"}], "\[IndentingNewLine]", 
          RowBox[{"For", "[", 
           RowBox[{
            RowBox[{"l", "=", 
             RowBox[{"k", "-", "1"}]}], ",", 
            RowBox[{"l", ">", "dimker"}], ",", 
            RowBox[{"l", "--"}], "\[IndentingNewLine]", ",", 
            RowBox[{"(*", " ", 
             RowBox[{
             "WE", " ", "use", " ", "the", " ", "order", " ", "of", " ", 
              "reduction", " ", "that", " ", "is", " ", "recommended", " ", 
              "by", " ", "LLL", " ", "or", " ", "Chou", " ", "Collins"}], " ",
              "*)"}], "\[IndentingNewLine]", 
            RowBox[{
             RowBox[{"j", "=", 
              RowBox[{"pp", "[", 
               RowBox[{"[", "l", "]"}], "]"}]}], ";", "\[IndentingNewLine]", 
             RowBox[{"u", "=", 
              RowBox[{"Quotient", "[", 
               RowBox[{
                RowBox[{"bb0", "[", 
                 RowBox[{"[", 
                  RowBox[{"k", ",", "j"}], "]"}], "]"}], ",", 
                RowBox[{"bb0", "[", 
                 RowBox[{"[", 
                  RowBox[{"l", ",", "j"}], "]"}], "]"}]}], "]"}]}], ";", 
             "\[IndentingNewLine]", 
             RowBox[{
              RowBox[{"bb0", "[", 
               RowBox[{"[", "k", "]"}], "]"}], "=", 
              RowBox[{
               RowBox[{"bb0", "[", 
                RowBox[{"[", "k", "]"}], "]"}], "-", 
               RowBox[{"u", " ", 
                RowBox[{"bb0", "[", 
                 RowBox[{"[", "l", "]"}], "]"}]}]}]}]}]}], 
           "\[IndentingNewLine]", "]"}]}], "\[IndentingNewLine]", "]"}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"k", "=", 
         RowBox[{"maxk", "+", "1"}]}]}]}], " ", 
      RowBox[{"(*", " ", 
       RowBox[{
        RowBox[{"Proceed", " ", "to", " ", "next", " ", "row"}], ",", " ", 
        RowBox[{
        "now", " ", "that", " ", "part", " ", "above", " ", "it", " ", "is", 
         " ", "in", " ", "HNF", " ", 
         RowBox[{"form", "."}]}]}], " ", "*)"}], "\[IndentingNewLine]", "]"}],
      ";", 
     RowBox[{"(*", " ", 
      RowBox[{"end", " ", "of", " ", "main", " ", "loop"}], " ", "*)"}], 
     "\[IndentingNewLine]", 
     RowBox[{"If", "[", 
      RowBox[{
       RowBox[{"uu", "=!=", "False"}], "\[IndentingNewLine]", ",", 
       RowBox[{"(*", " ", 
        RowBox[{"Extract", " ", "new", " ", "matrix", " ", "and", " ", 
         RowBox[{"transformation", "."}]}], " ", "*)"}], 
       "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"n", "=", 
         RowBox[{"n", "-", "m"}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"uu", "=", 
         RowBox[{
          RowBox[{
           RowBox[{"Take", "[", 
            RowBox[{"#", ",", "m"}], "]"}], "&"}], "/@", "bb0"}]}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"ans", "=", 
         RowBox[{
          RowBox[{
           RowBox[{"Take", "[", 
            RowBox[{"#", ",", 
             RowBox[{"-", "n"}]}], "]"}], "&"}], "/@", "bb0"}]}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"rank", "=", "0"}], ";", "\[IndentingNewLine]", 
        RowBox[{"For", "[", 
         RowBox[{
          RowBox[{"i", "=", "1"}], ",", 
          RowBox[{"i", "\[LessEqual]", "m"}], ",", 
          RowBox[{"i", "++"}], ",", 
          RowBox[{"If", "[", 
           RowBox[{
            RowBox[{
             RowBox[{"pp", "[", 
              RowBox[{"[", "i", "]"}], "]"}], ">", "m"}], ",", 
            RowBox[{"rank", "++"}]}], "]"}]}], "]"}]}], "\[IndentingNewLine]",
        ",", "\[IndentingNewLine]", 
       RowBox[{"ans", "=", "bb0"}]}], "\[IndentingNewLine]", "]"}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"{", 
      RowBox[{"ans", ",", "rank"}], "}"}]}]}], "\[IndentingNewLine]", 
   "]"}]}]}], "Input",
 InitializationCell->True],

Cell[BoxData[{
 RowBox[{
  RowBox[{
   RowBox[{"SetAttributes", "[", 
    RowBox[{"swap", ",", "HoldAll"}], "]"}], ";"}], 
  "\[IndentingNewLine]"}], "\n", 
 RowBox[{
  RowBox[{"swap", "[", 
   RowBox[{"kk_", ",", "bb_", ",", "pp_"}], "]"}], ":=", 
  RowBox[{"(*", " ", 
   RowBox[{
    RowBox[{
     RowBox[{
     "Swaps", " ", "row", " ", "k", " ", "with", " ", "row", " ", "k"}], "-", 
     "1"}], ",", " ", 
    RowBox[{"using", " ", "extended", " ", "GCD", " ", "if", " ", 
     RowBox[{"needed", "."}]}]}], " ", "*)"}], " ", "\[IndentingNewLine]", 
  RowBox[{"Module", "[", "\[IndentingNewLine]", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
     "i", ",", "j", ",", "l", ",", "t1", ",", "t2", ",", "e", ",", "x", ",", 
      "y", ",", 
      RowBox[{"k", "=", "kk"}]}], "}"}], "\[IndentingNewLine]", ",", 
    "\[IndentingNewLine]", 
    RowBox[{"If", "[", 
     RowBox[{
      RowBox[{
       RowBox[{"pp", "[", 
        RowBox[{"[", "k", "]"}], "]"}], "<", 
       RowBox[{"pp", "[", 
        RowBox[{"[", 
         RowBox[{"k", "-", "1"}], "]"}], "]"}]}], "\[IndentingNewLine]", ",", 
      
      RowBox[{"(*", " ", 
       RowBox[{
        RowBox[{"Row", " ", "k"}], "-", 
        RowBox[{"1", " ", "sticks", " ", "out", " ", 
         RowBox[{"further", "."}]}]}], " ", "*)"}], "\[IndentingNewLine]", 
      RowBox[{
       RowBox[{
        RowBox[{"{", 
         RowBox[{
          RowBox[{"bb", "[", 
           RowBox[{"[", 
            RowBox[{"k", "-", "1"}], "]"}], "]"}], ",", 
          RowBox[{"bb", "[", 
           RowBox[{"[", "k", "]"}], "]"}]}], "}"}], "=", 
        RowBox[{"{", 
         RowBox[{
          RowBox[{"bb", "[", 
           RowBox[{"[", "k", "]"}], "]"}], ",", 
          RowBox[{"bb", "[", 
           RowBox[{"[", 
            RowBox[{"k", "-", "1"}], "]"}], "]"}]}], "}"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{
          RowBox[{"pp", "[", 
           RowBox[{"[", 
            RowBox[{"k", "-", "1"}], "]"}], "]"}], ",", 
          RowBox[{"pp", "[", 
           RowBox[{"[", "k", "]"}], "]"}]}], "}"}], "=", 
        RowBox[{"{", 
         RowBox[{
          RowBox[{"pp", "[", 
           RowBox[{"[", "k", "]"}], "]"}], ",", 
          RowBox[{"pp", "[", 
           RowBox[{"[", 
            RowBox[{"k", "-", "1"}], "]"}], "]"}]}], "}"}]}], ";"}], 
      "\[IndentingNewLine]", ",", 
      RowBox[{"(*", " ", 
       RowBox[{"They", " ", "stick", " ", "out", " ", 
        RowBox[{"equally", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
      RowBox[{
       RowBox[{"j", "=", 
        RowBox[{"pp", "[", 
         RowBox[{"[", "k", "]"}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{"e", ",", 
          RowBox[{"{", 
           RowBox[{"x", ",", "y"}], "}"}]}], "}"}], "=", 
        RowBox[{"ExtendedGCD", "[", 
         RowBox[{
          RowBox[{"bb", "[", 
           RowBox[{"[", 
            RowBox[{
             RowBox[{"k", "-", "1"}], ",", "j"}], "]"}], "]"}], ",", 
          RowBox[{"bb", "[", 
           RowBox[{"[", 
            RowBox[{"k", ",", "j"}], "]"}], "]"}]}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"t1", "=", 
        RowBox[{"Quotient", "[", 
         RowBox[{
          RowBox[{"bb", "[", 
           RowBox[{"[", 
            RowBox[{"k", ",", "j"}], "]"}], "]"}], ",", "e"}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"t2", "=", 
        RowBox[{"-", 
         RowBox[{"Quotient", "[", 
          RowBox[{
           RowBox[{"bb", "[", 
            RowBox[{"[", 
             RowBox[{
              RowBox[{"k", "-", "1"}], ",", "j"}], "]"}], "]"}], ",", "e"}], 
          "]"}]}]}], ";", "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{
          RowBox[{"bb", "[", 
           RowBox[{"[", 
            RowBox[{"k", "-", "1"}], "]"}], "]"}], ",", 
          RowBox[{"bb", "[", 
           RowBox[{"[", "k", "]"}], "]"}]}], "}"}], "=", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"t1", ",", "t2"}], "}"}], ",", 
           RowBox[{"{", 
            RowBox[{"x", ",", "y"}], "}"}]}], "}"}], ".", 
         RowBox[{"{", 
          RowBox[{
           RowBox[{"bb", "[", 
            RowBox[{"[", 
             RowBox[{"k", "-", "1"}], "]"}], "]"}], ",", 
           RowBox[{"bb", "[", 
            RowBox[{"[", "k", "]"}], "]"}]}], "}"}]}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"For", "[", 
        RowBox[{
         RowBox[{"i", "=", "0"}], ",", "True", ",", 
         RowBox[{"i", "++"}], ",", "\[IndentingNewLine]", 
         RowBox[{
          RowBox[{"If", "[", 
           RowBox[{
            RowBox[{
             RowBox[{"(", 
              RowBox[{"j", ">", "0"}], ")"}], "&&", 
             RowBox[{"(", 
              RowBox[{
               RowBox[{"bb", "[", 
                RowBox[{"[", 
                 RowBox[{"k", ",", "j"}], "]"}], "]"}], "<", "0"}], ")"}]}], 
            ",", 
            RowBox[{
             RowBox[{"bb", "[", 
              RowBox[{"[", "k", "]"}], "]"}], "=", 
             RowBox[{"-", 
              RowBox[{"bb", "[", 
               RowBox[{"[", "k", "]"}], "]"}]}]}]}], "]"}], ";", 
          RowBox[{"(*", " ", 
           RowBox[{"Keep", " ", "diagonal", " ", 
            RowBox[{"positive", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
          RowBox[{"If", "[", 
           RowBox[{
            RowBox[{"i", ">", "0"}], ",", 
            RowBox[{"Break", "[", "]"}]}], "]"}], ";", "\[IndentingNewLine]", 
          
          RowBox[{"k", "--"}], ";", 
          RowBox[{"(*", " ", 
           RowBox[{
           "Look", " ", "again", " ", "how", " ", "far", " ", "it", " ", 
            "sticks", " ", 
            RowBox[{"out", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
          RowBox[{"While", "[", 
           RowBox[{
            RowBox[{
             RowBox[{"(", 
              RowBox[{"j", ">", "0"}], ")"}], "&&", 
             RowBox[{"(", 
              RowBox[{
               RowBox[{"bb", "[", 
                RowBox[{"[", 
                 RowBox[{"k", ",", "j"}], "]"}], "]"}], "\[Equal]", "0"}], 
              ")"}]}], ",", 
            RowBox[{"j", "--"}]}], "]"}], ";", "\[IndentingNewLine]", 
          RowBox[{
           RowBox[{"pp", "[", 
            RowBox[{"[", "k", "]"}], "]"}], "=", "j"}]}]}], 
        "\[IndentingNewLine]", "]"}]}]}], "\[IndentingNewLine]", "]"}]}], 
   "\[IndentingNewLine]", "]"}]}]}], "Input",
 InitializationCell->True]
}, Closed]],

Cell[CellGroupData[{

Cell["Examples", "Section"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"?", "hnf"}]], "Input"],

Cell[BoxData[
 StyleBox["\<\"{newmatrix,rank}=hnf[mat] gives a lower triangular Hermite \
Normal Form of the integral matrix mat, together with its \
rank.\\n\\n{newmatrix,rank}=hnf[matrix,symbol] also assigns to symbol the \
matrix trans so that trans.mat=newmatrix.\"\>", "MSG"]], "Print", "PrintUsage",
 CellChangeTimes->{3.451454360042295*^9},
 CellTags->"Info3451461559-9264477"]
}, Open  ]],

Cell[BoxData[
 RowBox[{
  RowBox[{"ma", "=", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"990519", ",", 
       RowBox[{"-", "4051508"}], ",", 
       RowBox[{"-", "3802647"}], ",", 
       RowBox[{"-", "43245"}], ",", 
       RowBox[{"-", "369337"}], ",", "1967100"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"1598245", ",", 
       RowBox[{"-", "8116013"}], ",", 
       RowBox[{"-", "6067138"}], ",", 
       RowBox[{"-", "3323116"}], ",", 
       RowBox[{"-", "2053036"}], ",", "3161362"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"1786244", ",", "1069431", ",", 
       RowBox[{"-", "465693"}], ",", 
       RowBox[{"-", "227421"}], ",", 
       RowBox[{"-", "2029817"}], ",", 
       RowBox[{"-", "542818"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"1084810", ",", "1537944", ",", "260218", ",", 
       RowBox[{"-", "1057178"}], ",", 
       RowBox[{"-", "1016978"}], ",", 
       RowBox[{"-", "362744"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"824048", ",", 
       RowBox[{"-", "2096515"}], ",", 
       RowBox[{"-", "2199740"}], ",", 
       RowBox[{"-", "427760"}], ",", 
       RowBox[{"-", "447464"}], ",", "1118810"}], "}"}], ",", 
     "\[IndentingNewLine]", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "90848"}], ",", "5193882", ",", "1635132", ",", "6421956",
        ",", "2423012", ",", 
       RowBox[{"-", "1147532"}]}], "}"}]}], "}"}]}], ";"}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"new", ",", "rank"}], "}"}], "=", 
   RowBox[{"hnf", "[", 
    RowBox[{"ma", ",", "u"}], "]"}]}], ";"}]], "Input"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"u", ".", "ma"}], "\[Equal]", "new"}]], "Input"],

Cell[BoxData["True"], "Output",
 CellChangeTimes->{3.451454360254587*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"hnf", "[", "ma", "]"}], "[", 
   RowBox[{"[", "1", "]"}], "]"}], "\[Equal]", "new"}]], "Input"],

Cell[BoxData["True"], "Output",
 CellChangeTimes->{3.451454360290387*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "ma", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"990519", 
      RowBox[{"-", "4051508"}], 
      RowBox[{"-", "3802647"}], 
      RowBox[{"-", "43245"}], 
      RowBox[{"-", "369337"}], "1967100"},
     {"1598245", 
      RowBox[{"-", "8116013"}], 
      RowBox[{"-", "6067138"}], 
      RowBox[{"-", "3323116"}], 
      RowBox[{"-", "2053036"}], "3161362"},
     {"1786244", "1069431", 
      RowBox[{"-", "465693"}], 
      RowBox[{"-", "227421"}], 
      RowBox[{"-", "2029817"}], 
      RowBox[{"-", "542818"}]},
     {"1084810", "1537944", "260218", 
      RowBox[{"-", "1057178"}], 
      RowBox[{"-", "1016978"}], 
      RowBox[{"-", "362744"}]},
     {"824048", 
      RowBox[{"-", "2096515"}], 
      RowBox[{"-", "2199740"}], 
      RowBox[{"-", "427760"}], 
      RowBox[{"-", "447464"}], "1118810"},
     {
      RowBox[{"-", "90848"}], "5193882", "1635132", "6421956", "2423012", 
      RowBox[{"-", "1147532"}]}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.4514543603455477`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "new", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"0", "0", "0", "0", "0", "0"},
     {"0", "0", "0", "0", "0", "0"},
     {"7957707264", "15915414528", "0", "0", "0", "0"},
     {"617299785", "1234599394", 
      RowBox[{"-", "154"}], "440", "0", "0"},
     {"1606404357", "3212808586", 
      RowBox[{"-", "113"}], "325", "1", "0"},
     {"4612883786", "9225767525", 
      RowBox[{"-", "40"}], "104", "0", "2"}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.451454360395151*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "u", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {
      RowBox[{"-", "56489124892"}], 
      RowBox[{"-", "2642575114"}], "6570408110", 
      RowBox[{"-", "31201137677"}], "99858246196", "0"},
     {
      RowBox[{"-", "51427413573"}], 
      RowBox[{"-", "2405786993"}], "5981666301", 
      RowBox[{"-", "28405357902"}], "90910442188", "12"},
     {
      RowBox[{"-", "171531944"}], 
      RowBox[{"-", "8028396"}], "19948520", 
      RowBox[{"-", "94735486"}], "303237226", "1"},
     {
      RowBox[{"-", "24510371581"}], 
      RowBox[{"-", "1146601504"}], "2850869649", 
      RowBox[{"-", "13538029544"}], "43328034909", "3"},
     {
      RowBox[{"-", "48579325552"}], 
      RowBox[{"-", "2272553565"}], "5650396645", 
      RowBox[{"-", "26832246603"}], "85875757576", "11"},
     {
      RowBox[{"-", "47995909587"}], 
      RowBox[{"-", "2245262773"}], "5582536831", 
      RowBox[{"-", "26510000186"}], "84844433049", "9"}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.451454360445668*^9}]
}, Open  ]],

Cell["\<\
The above matrix \"new\" is in lower triangular HNF form. A matrix is in \
lower triangular HNF form if it is either zero, or there is a \"first \
pivot\", in the example the entry 15915414528, which
is positive
has zero rows above it
has zeroes to the right of it in its row
has nonegative entries in its column, all other entries being smaller
has to its right a matrix in lower triangular HNF form. In the example this \
submatrix is:\
\>", "Text",
 FontSize->14],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", 
  RowBox[{
   RowBox[{
    RowBox[{"Take", "[", 
     RowBox[{"#", ",", 
      RowBox[{"-", "4"}]}], "]"}], "&"}], "/@", "new"}], "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"0", "0", "0", "0"},
     {"0", "0", "0", "0"},
     {"0", "0", "0", "0"},
     {
      RowBox[{"-", "154"}], "440", "0", "0"},
     {
      RowBox[{"-", "113"}], "325", "1", "0"},
     {
      RowBox[{"-", "40"}], "104", "0", "2"}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.451454360495751*^9}]
}, Open  ]],

Cell["\<\
If you prefer a more traditional upper triangular (echelon) Hermite Normal \
Form, then you may proceed like this:\
\>", "Text",
 FontSize->14],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"new", ",", "rank"}], "}"}], "=", 
   RowBox[{"hnf", "[", 
    RowBox[{
     RowBox[{"Reverse", "[", 
      RowBox[{"Reverse", "/@", "ma"}], "]"}], ",", "u"}], "]"}]}], ";", 
  RowBox[{"new", "=", 
   RowBox[{"Reverse", "[", 
    RowBox[{"Reverse", "/@", "new"}], "]"}]}], ";", 
  RowBox[{"u", "=", 
   RowBox[{"Reverse", "[", 
    RowBox[{"Reverse", "/@", "u"}], "]"}]}], ";", 
  RowBox[{
   RowBox[{"u", ".", "ma"}], "\[Equal]", "new"}]}]], "Input"],

Cell[BoxData["True"], "Output",
 CellChangeTimes->{3.451454360540586*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "ma", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"990519", 
      RowBox[{"-", "4051508"}], 
      RowBox[{"-", "3802647"}], 
      RowBox[{"-", "43245"}], 
      RowBox[{"-", "369337"}], "1967100"},
     {"1598245", 
      RowBox[{"-", "8116013"}], 
      RowBox[{"-", "6067138"}], 
      RowBox[{"-", "3323116"}], 
      RowBox[{"-", "2053036"}], "3161362"},
     {"1786244", "1069431", 
      RowBox[{"-", "465693"}], 
      RowBox[{"-", "227421"}], 
      RowBox[{"-", "2029817"}], 
      RowBox[{"-", "542818"}]},
     {"1084810", "1537944", "260218", 
      RowBox[{"-", "1057178"}], 
      RowBox[{"-", "1016978"}], 
      RowBox[{"-", "362744"}]},
     {"824048", 
      RowBox[{"-", "2096515"}], 
      RowBox[{"-", "2199740"}], 
      RowBox[{"-", "427760"}], 
      RowBox[{"-", "447464"}], "1118810"},
     {
      RowBox[{"-", "90848"}], "5193882", "1635132", "6421956", "2423012", 
      RowBox[{"-", "1147532"}]}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.4514543605950937`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "new", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"1", "0", "0", "8943649870818", 
      RowBox[{"-", "1277664267262"}], 
      RowBox[{"-", "2271403141796"}]},
     {"0", "1", "0", "8121001086444", 
      RowBox[{"-", "1160143012348"}], 
      RowBox[{"-", "2062476466398"}]},
     {"0", "0", "1", "1304088368557", 
      RowBox[{"-", "186298338367"}], 
      RowBox[{"-", "331197045984"}]},
     {"0", "0", "0", "11029382267904", 
      RowBox[{"-", "1575626038272"}], 
      RowBox[{"-", "2801112956928"}]},
     {"0", "0", "0", "0", "0", "0"},
     {"0", "0", "0", "0", "0", "0"}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.45145436064534*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "u", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"0", "1160661967383", 
      RowBox[{"-", "402774640356"}], "958706785419", 
      RowBox[{"-", "2577000444333"}], "572506242412"},
     {"0", "1159207084284", 
      RowBox[{"-", "402270191576"}], "957505649050", 
      RowBox[{"-", "2573770053475"}], "571788574982"},
     {"0", "401563846232", 
      RowBox[{"-", "139352224409"}], "331693054390", 
      RowBox[{"-", "891585915583"}], "198074657145"},
     {"0", "103903639810", 
      RowBox[{"-", "36051413906"}], "85816880019", 
      RowBox[{"-", "230697410462"}], "51251771575"},
     {"1", "858445509387", 
      RowBox[{"-", "297902516315"}], "709080858371", 
      RowBox[{"-", "1905992647328"}], "423435163380"},
     {"0", "1374269492566", 
      RowBox[{"-", "476906612538"}], "1135154393337", 
      RowBox[{"-", "3051268274612"}], "677869498704"}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.451454360695683*^9}]
}, Open  ]],

Cell["Let us try a few random cases.", "Text",
 FontSize->14],

Cell[BoxData[
 RowBox[{
  RowBox[{"mat", "[", 
   RowBox[{"n_", ",", "m_", ",", "d_"}], "]"}], ":=", 
  RowBox[{"Table", "[", 
   RowBox[{
    RowBox[{"RandomInteger", "[", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "d"}], ",", "d"}], "}"}], "]"}], ",", 
    RowBox[{"{", 
     RowBox[{"i", ",", "m"}], "}"}], ",", 
    RowBox[{"{", 
     RowBox[{"j", ",", "n"}], "}"}]}], "]"}]}]], "Input",
 InitializationCell->True],

Cell["\<\
First an example where the normal form itself is not so favorable. Then of \
course the algorithm can't keep the integers smaller than that.\
\>", "Text",
 FontSize->14],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"new", ",", "rank"}], "}"}], "=", 
   RowBox[{"hnf", "[", 
    RowBox[{
     RowBox[{"ma", "=", 
      RowBox[{"mat", "[", 
       RowBox[{"60", ",", "40", ",", "1000"}], "]"}]}], ",", "u"}], "]"}]}], 
  ";"}]], "Input"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "new", "]"}], "]"}]], "Input"],

Cell[BoxData[\
"14413754780703279827201680206243115758033146490452766716932828264370438205185\
3523786025270075849261361293539788907729883742461182847134"], "Output",
 CellChangeTimes->{3.4514543618802013`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "u", "]"}], "]"}]], "Input"],

Cell[BoxData[\
"46324674865323404862190334580677959628170963595073867200148247215720564093706\
641586143086911500396593703950857515299185844403277846"], "Output",
 CellChangeTimes->{3.451454361923538*^9}]
}, Open  ]],

Cell["Next an example where the normal form itself is fine.", "Text",
 FontSize->14],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"new", ",", "rank"}], "}"}], "=", 
   RowBox[{"hnf", "[", 
    RowBox[{
     RowBox[{"ma", "=", 
      RowBox[{"mat", "[", 
       RowBox[{"40", ",", "60", ",", "1000"}], "]"}]}], ",", "u"}], "]"}]}], 
  ";"}]], "Input"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "new", "]"}], "]"}]], "Input"],

Cell[BoxData["1"], "Output",
 CellChangeTimes->{3.451454365113855*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "u", "]"}], "]"}]], "Input"],

Cell[BoxData[\
"33661119679107890113977684752379426832065693787693422978707636073761153044619\
5591520151407075863760796834943375627341086207459591232287"], "Output",
 CellChangeTimes->{3.4514543651616697`*^9}]
}, Open  ]],

Cell["\<\
You see that the entries of the transformation matrix get as bad as in the \
previous case. One has an estimate for the bitlength of entries of the \
transformation matrix that is roughly the number of rows of the input matrix \
times the the bitlength of its largest entry .\
\>", "Text",
 FontSize->14],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Log", "[", 
  RowBox[{"N", "[", 
   RowBox[{"Max", "[", "u", "]"}], "]"}], "]"}]], "Input"],

Cell[BoxData["309.7601608207998`"], "Output",
 CellChangeTimes->{3.4514543652117357`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Log", "[", 
  RowBox[{"N", "[", 
   RowBox[{"Max", "[", "ma", "]"}], "]"}], "]"}]], "Input"],

Cell[BoxData["6.907755278982137`"], "Output",
 CellChangeTimes->{3.45145436526089*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"Length", "[", "ma", "]"}], " ", 
  RowBox[{"Log", "[", 
   RowBox[{
    RowBox[{"Length", "[", "ma", "]"}], 
    RowBox[{"N", "[", 
     RowBox[{"Max", "[", "ma", "]"}], "]"}]}], "]"}]}]], "Input"],

Cell[BoxData["660.1259904722543`"], "Output",
 CellChangeTimes->{3.451454365310986*^9}]
}, Open  ]],

Cell["\<\
To see how bad it gets when you are stupid and wait with the reductions until \
the end, let us consider the variant where one does not do any of these \
reductions.\
\>", "Text",
 FontSize->14],

Cell[BoxData[{
 RowBox[{
  RowBox[{"SetAttributes", "[", 
   RowBox[{"hnfstupid", ",", "HoldAll"}], "]"}], 
  "\n"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"hnfstupid", "::", "usage"}], ":=", 
   "\"\<{newmatrix,rank}=hnf[mat]  gives a lower triangular Normal Form of \
the integral matrix mat, together with its rank. \n\
{newmatrix,rank}=hnf[matrix,symbol] also assigns to symbol the matrix trans \
so that trans.mat=newmatrix.\>\""}], "\n"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"hnfstupid", "[", 
   RowBox[{"bb_", ",", 
    RowBox[{"uu_:", "False"}]}], "]"}], ":=", 
  RowBox[{"Module", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"u", ",", 
      RowBox[{"m", "=", 
       RowBox[{"Length", "[", "bb", "]"}]}], ",", 
      RowBox[{"n", "=", 
       RowBox[{"Length", "[", 
        RowBox[{"bb", "[", 
         RowBox[{"[", "1", "]"}], "]"}], "]"}]}], ",", "i", ",", "j", ",", 
      "l", ",", "pp", ",", "bb0", ",", 
      RowBox[{"rank", "=", "0"}], ",", 
      RowBox[{"dimker", "=", "0"}], ",", 
      RowBox[{"k", "=", "1"}], ",", 
      RowBox[{"maxk", "=", "0"}], ",", "ans"}], "}"}], ",", 
    RowBox[{
     RowBox[{"pp", "=", 
      RowBox[{"0", " ", 
       RowBox[{"Range", "[", "m", "]"}]}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"If", "[", 
      RowBox[{
       RowBox[{"uu", "=!=", "False"}], ",", 
       RowBox[{
        RowBox[{"bb0", "=", 
         RowBox[{"Transpose", "[", 
          RowBox[{"Join", "[", 
           RowBox[{
            RowBox[{"IdentityMatrix", "[", "m", "]"}], ",", 
            RowBox[{"Transpose", "[", "bb", "]"}]}], "]"}], "]"}]}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"n", "=", 
         RowBox[{"n", "+", "m"}]}]}], ",", 
       RowBox[{"bb0", "=", "bb"}]}], "]"}], ";", "\[IndentingNewLine]", 
     RowBox[{"For", "[", 
      RowBox[{
       RowBox[{"i", "=", "1"}], ",", 
       RowBox[{"i", "\[LessEqual]", "m"}], ",", 
       RowBox[{"i", "++"}], ",", 
       RowBox[{
        RowBox[{"j", "=", "n"}], ";", "\[IndentingNewLine]", 
        RowBox[{"While", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"(", 
            RowBox[{"j", ">", "0"}], ")"}], "&&", 
           RowBox[{"(", 
            RowBox[{
             RowBox[{"bb0", "[", 
              RowBox[{"[", 
               RowBox[{"i", ",", "j"}], "]"}], "]"}], "\[Equal]", "0"}], 
            ")"}]}], ",", 
          RowBox[{"j", "--"}]}], "]"}], ";", "\[IndentingNewLine]", 
        RowBox[{
         RowBox[{"pp", "[", 
          RowBox[{"[", "i", "]"}], "]"}], "=", "j"}], ";"}]}], "]"}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"While", "[", 
      RowBox[{
       RowBox[{"k", "\[LessEqual]", "m"}], ",", 
       RowBox[{
        RowBox[{"maxk", "=", "k"}], ";", "\[IndentingNewLine]", 
        RowBox[{"While", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"(", 
            RowBox[{"k", ">", 
             RowBox[{"dimker", "+", "1"}]}], ")"}], "&&", 
           RowBox[{"(", 
            RowBox[{
             RowBox[{"pp", "[", 
              RowBox[{"[", "k", "]"}], "]"}], "\[LessEqual]", 
             RowBox[{"pp", "[", 
              RowBox[{"[", 
               RowBox[{"k", "-", "1"}], "]"}], "]"}]}], ")"}]}], ",", 
          RowBox[{
           RowBox[{"swap", "[", 
            RowBox[{"k", ",", "bb0", ",", "pp"}], "]"}], ";", 
           "\[IndentingNewLine]", 
           RowBox[{"k", "--"}], ";"}]}], "]"}], ";", "\[IndentingNewLine]", 
        RowBox[{"If", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"pp", "[", 
            RowBox[{"[", "k", "]"}], "]"}], "\[Equal]", "0"}], ",", 
          RowBox[{"dimker", "++"}], ",", 
          RowBox[{"rank", "++"}]}], "]"}], ";", "\[IndentingNewLine]", 
        RowBox[{"For", "[", 
         RowBox[{"Null", ",", 
          RowBox[{"k", "\[LessEqual]", "maxk"}], ",", 
          RowBox[{"k", "++"}], ",", 
          RowBox[{"For", "[", 
           RowBox[{
            RowBox[{"l", "=", 
             RowBox[{"k", "-", "1"}]}], ",", 
            RowBox[{"l", ">", "dimker"}], ",", 
            RowBox[{"l", "--"}], ",", 
            RowBox[{
             RowBox[{"j", "=", 
              RowBox[{"pp", "[", 
               RowBox[{"[", "l", "]"}], "]"}]}], ";", "\[IndentingNewLine]", 
             RowBox[{"u", "=", 
              RowBox[{"Quotient", "[", 
               RowBox[{
                RowBox[{"bb0", "[", 
                 RowBox[{"[", 
                  RowBox[{"k", ",", "j"}], "]"}], "]"}], ",", 
                RowBox[{"bb0", "[", 
                 RowBox[{"[", 
                  RowBox[{"l", ",", "j"}], "]"}], "]"}]}], "]"}]}], ";"}]}], 
           "\[IndentingNewLine]", 
           RowBox[{"(*", " ", 
            RowBox[{
             RowBox[{"bb0", "[", 
              RowBox[{"[", "k", "]"}], "]"}], "=", 
             RowBox[{
              RowBox[{"bb0", "[", 
               RowBox[{"[", "k", "]"}], "]"}], "-", 
              RowBox[{"u", " ", 
               RowBox[{"bb0", "[", 
                RowBox[{"[", "l", "]"}], "]"}]}]}]}], " ", "*)"}], 
           "\[IndentingNewLine]", "]"}]}], " ", "]"}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"k", "=", 
         RowBox[{"maxk", "+", "1"}]}]}]}], "]"}], ";", "\[IndentingNewLine]", 
     
     RowBox[{"If", "[", 
      RowBox[{
       RowBox[{"uu", "=!=", "False"}], ",", 
       RowBox[{
        RowBox[{"n", "=", 
         RowBox[{"n", "-", "m"}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"uu", "=", 
         RowBox[{
          RowBox[{
           RowBox[{"Take", "[", 
            RowBox[{"#", ",", "m"}], "]"}], "&"}], "/@", "bb0"}]}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"ans", "=", 
         RowBox[{
          RowBox[{
           RowBox[{"Take", "[", 
            RowBox[{"#", ",", 
             RowBox[{"-", "n"}]}], "]"}], "&"}], "/@", "bb0"}]}], ";", 
        "\[IndentingNewLine]", 
        RowBox[{"rank", "=", "0"}], ";", "\[IndentingNewLine]", 
        RowBox[{"For", "[", 
         RowBox[{
          RowBox[{"i", "=", "1"}], ",", 
          RowBox[{"i", "\[LessEqual]", "m"}], ",", 
          RowBox[{"i", "++"}], ",", 
          RowBox[{"If", "[", 
           RowBox[{
            RowBox[{
             RowBox[{"pp", "[", 
              RowBox[{"[", "i", "]"}], "]"}], ">", "m"}], ",", 
            RowBox[{"rank", "++"}]}], "]"}]}], "]"}]}], ",", 
       RowBox[{"ans", "=", "bb0"}]}], "]"}], ";", "\[IndentingNewLine]", 
     RowBox[{"{", 
      RowBox[{"ans", ",", "rank"}], "}"}]}]}], "]"}]}]}], "Input"],

Cell["Now let us see how bad it gets.", "Text",
 FontSize->14],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"new", ",", "rank"}], "}"}], "=", 
   RowBox[{"hnfstupid", "[", 
    RowBox[{
     RowBox[{"ma", "=", 
      RowBox[{"mat", "[", 
       RowBox[{"10", ",", "20", ",", "1000"}], "]"}]}], ",", "u"}], "]"}]}], 
  ";"}]], "Input"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "new", "]"}], "]"}]], "Input"],

Cell[BoxData[\
"73117063833922396428386246346393655324822649798426187077579634607318001340481\
533773875772520405009687039850753402451296447610308800588611257040584446031799\
0063074006070044414"], "Output",
 CellChangeTimes->{3.451454365392359*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "u", "]"}], "]"}]], "Input"],

Cell[BoxData[\
"66497115906601519589471830495063302253588998089981844306533037905155522164156\
854571897085083340013815507508690119038278350162706848191783686661675301848578\
298899191447045613365589823720043392856240143863963543640164988690814504554069\
046961735126056095002484421591936448639592340163138135283190698397384063580684\
984630463622065221423223516686973487676905853286849459969736023243280139249961\
040439565250637467550484579104575724837158098131110691231481182636225713547604\
278606223111692560596514109474550289222958477030906680898076796672881286055047\
253791087016232038489929872721420275261322945544628636671280822186275204671560\
870644196168398121918154415782166879282263195536744105532546798000778510153303\
765069534688791572009017198184808761893229120956594902400901952709257040484349\
051044846751"], "Output",
 CellChangeTimes->{3.451454365439638*^9}]
}, Open  ]],

Cell["Compare that with", "Text",
 FontSize->14],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"new", ",", "rank"}], "}"}], "=", 
   RowBox[{"hnf", "[", 
    RowBox[{"ma", ",", "u"}], "]"}]}], ";"}]], "Input"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "new", "]"}], "]"}]], "Input"],

Cell[BoxData["1"], "Output",
 CellChangeTimes->{3.451454365521248*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "u", "]"}], "]"}]], "Input"],

Cell[BoxData["1344287904119868709694947130198"], "Output",
 CellChangeTimes->{3.4514543655569687`*^9}]
}, Open  ]],

Cell["We leave it to you to explore larger cases.", "Text",
 FontSize->14]
}, Closed]],

Cell[CellGroupData[{

Cell["Better transformation matrices.", "Section"],

Cell[TextData[{
 "Following Havas-Majewski-Matthews we can use LLL to improve on the \
transformation matrix when there are zero rows in the normal form. The \
difference with their approach is that we postpone this improving until our \
lightweight ",
 StyleBox["hnf",
  FontFamily->"Bold"],
 " has run its course. We believe this often makes sense. But we did not run \
tests to compare the two approaches. Note that we will be mixing the compiled \
code LatticeReduce with uncompiled code."
}], "Text",
 FontSize->14],

Cell[CellGroupData[{

Cell["The hnfLLL code", "Subsection"],

Cell[BoxData[{
 RowBox[{
  RowBox[{
   RowBox[{"SetAttributes", "[", 
    RowBox[{"hnfLLL", ",", "HoldAll"}], "]"}], ";"}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{
    RowBox[{"hnfLLL", "::", "usage"}], ":=", 
    "\"\<{newmatrix,rank}=hnfLLL[mat,symbol] gives a lower triangular Hermite \
Normal Form of the integral matrix mat, together with its rank.\\n\nIt also \
assigns to symbol an optimized matrix trans so that \
trans.mat=newmatrix.\>\""}], ";"}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"hnfLLL", "[", 
    RowBox[{"bb_", ",", "uu_"}], "]"}], ":=", "\[IndentingNewLine]", 
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"u", ",", 
       RowBox[{"m", "=", 
        RowBox[{"Length", "[", "bb", "]"}]}], ",", "i", ",", "j", ",", "k", 
       ",", "l", ",", "dd", ",", "lam", ",", "rank", ",", "dimker", ",", 
       "ans"}], "}"}], ",", "\[IndentingNewLine]", 
     RowBox[{
      RowBox[{"dd", "=", 
       RowBox[{"Range", "[", 
        RowBox[{"m", "+", "1"}], "]"}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"lam", "=", 
       RowBox[{"0", " ", 
        RowBox[{"IdentityMatrix", "[", "m", "]"}]}]}], ";", 
      "\[IndentingNewLine]", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"ans", ",", "rank"}], "}"}], "=", 
       RowBox[{"hnf", "[", 
        RowBox[{"bb", ",", "uu"}], "]"}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"dimker", "=", 
       RowBox[{"m", "-", "rank"}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"If", "[", 
       RowBox[{
        RowBox[{"dimker", ">", "0"}], ",", 
        RowBox[{"(*", " ", 
         RowBox[{
         "otherwise", " ", "there", " ", "is", " ", "no", " ", "point", " ", 
          "calling", " ", "hnfLLL"}], " ", "*)"}], "\[IndentingNewLine]", 
        RowBox[{"uu", "=", 
         RowBox[{"Join", "[", 
          RowBox[{
           RowBox[{"LatticeReduce", "[", 
            RowBox[{"Take", "[", 
             RowBox[{"uu", ",", "dimker"}], "]"}], "]"}], ",", 
           RowBox[{"Take", "[", 
            RowBox[{"uu", ",", 
             RowBox[{"-", "rank"}]}], "]"}]}], "]"}]}]}], " ", 
       RowBox[{"(*", " ", 
        RowBox[{"LatticeReduce", " ", "the", " ", 
         RowBox[{"nullspace", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
       "]"}], ";", "\[IndentingNewLine]", 
      RowBox[{"For", "[", 
       RowBox[{
        RowBox[{"k", "=", "1"}], ",", 
        RowBox[{"k", "\[LessEqual]", "dimker"}], ",", 
        RowBox[{"k", "++"}], ",", 
        RowBox[{"(*", " ", 
         RowBox[{"Build", " ", "the", " ", "GramSchmidt", " ", 
          RowBox[{"table", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
        RowBox[{
         RowBox[{"For", "[", 
          RowBox[{
           RowBox[{"i", "=", "1"}], ",", 
           RowBox[{"i", "\[LessEqual]", "k"}], ",", 
           RowBox[{"i", "++"}], ",", 
           RowBox[{"gramS", "[", 
            RowBox[{"uu", ",", "dd", ",", "lam", ",", "i", ",", "k"}], 
            "]"}]}], "]"}], ";", "\[IndentingNewLine]", 
         RowBox[{"For", "[", 
          RowBox[{
           RowBox[{"l", "=", 
            RowBox[{"k", "-", "1"}]}], ",", 
           RowBox[{"l", ">", "0"}], ",", 
           RowBox[{"l", "--"}], ",", 
           RowBox[{"reduce", "[", 
            RowBox[{"k", ",", "l", ",", "dd", ",", "lam", ",", "uu"}], 
            "]"}]}], "]"}]}]}], " ", 
       RowBox[{"(*", " ", 
        RowBox[{"This", " ", "should", " ", "not", " ", "be", " ", 
         RowBox[{"necessary", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
       "]"}], ";", "\[IndentingNewLine]", 
      RowBox[{"For", "[", 
       RowBox[{
        RowBox[{"k", "=", 
         RowBox[{"dimker", "+", "1"}]}], ",", 
        RowBox[{"k", "\[LessEqual]", "m"}], ",", 
        RowBox[{"k", "++"}], ",", 
        RowBox[{"(*", " ", 
         RowBox[{
          RowBox[{"Build", " ", "more", " ", "of", " ", "the", " ", "Gram"}], 
          "-", 
          RowBox[{"Schmidt", " ", 
           RowBox[{"table", "."}]}]}], " ", "*)"}], "\[IndentingNewLine]", 
        RowBox[{
         RowBox[{"For", "[", 
          RowBox[{
           RowBox[{"l", "=", "1"}], ",", 
           RowBox[{"l", "\[LessEqual]", "dimker"}], ",", 
           RowBox[{"l", "++"}], ",", 
           RowBox[{"gramS", "[", 
            RowBox[{"uu", ",", "dd", ",", "lam", ",", "l", ",", "k"}], 
            "]"}]}], "]"}], ";", "\[IndentingNewLine]", 
         RowBox[{"For", "[", 
          RowBox[{
           RowBox[{"l", "=", "dimker"}], ",", 
           RowBox[{"l", ">", "0"}], ",", 
           RowBox[{"l", "--"}], ",", 
           RowBox[{"reduce", "[", 
            RowBox[{"k", ",", "l", ",", "dd", ",", "lam", ",", "uu"}], 
            "]"}]}], "]"}]}]}], " ", 
       RowBox[{"(*", " ", 
        RowBox[{"This", " ", "should", " ", "help", " ", "a", " ", 
         RowBox[{"lot", "."}]}], " ", "*)"}], "\[IndentingNewLine]", "]"}], 
      ";", "\[IndentingNewLine]", 
      RowBox[{"{", 
       RowBox[{"ans", ",", "rank"}], "}"}]}]}], "\[IndentingNewLine]", 
    "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"SetAttributes", "[", 
    RowBox[{"gramS", ",", "HoldAll"}], "]"}], ";"}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"gramS", "[", 
    RowBox[{"uu_", ",", "dd_", ",", "lam_", ",", "low_", ",", "up_"}], "]"}], 
   ":=", "\[IndentingNewLine]", 
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"u", ",", "t1", ",", "t2", ",", "i"}], "}"}], ",", 
     RowBox[{"(*", " ", 
      RowBox[{
       RowBox[{"Compute", " ", "entry", " ", "of", " ", "Gram"}], "-", 
       RowBox[{"Schmidt", " ", 
        RowBox[{"table", "."}]}]}], " ", "*)"}], "\[IndentingNewLine]", 
     RowBox[{
      RowBox[{"u", "=", 
       RowBox[{
        RowBox[{"uu", "[", 
         RowBox[{"[", "low", "]"}], "]"}], ".", 
        RowBox[{"uu", "[", 
         RowBox[{"[", "up", "]"}], "]"}]}]}], ";", "\[IndentingNewLine]", 
      RowBox[{"For", "[", 
       RowBox[{
        RowBox[{"i", "=", "1"}], ",", 
        RowBox[{"i", "<", "low"}], ",", 
        RowBox[{"i", "++"}], ",", "\[IndentingNewLine]", 
        RowBox[{
         RowBox[{"t1", "=", 
          RowBox[{"u", " ", 
           RowBox[{"dd", "[", 
            RowBox[{"[", 
             RowBox[{"i", "+", "1"}], "]"}], "]"}]}]}], ";", 
         "\[IndentingNewLine]", 
         RowBox[{"t2", "=", 
          RowBox[{
           RowBox[{"lam", "[", 
            RowBox[{"[", 
             RowBox[{"up", ",", "i"}], "]"}], "]"}], " ", 
           RowBox[{"lam", "[", 
            RowBox[{"[", 
             RowBox[{"low", ",", "i"}], "]"}], "]"}]}]}], ";", 
         "\[IndentingNewLine]", 
         RowBox[{"t1", "=", 
          RowBox[{"t1", "-", "t2"}]}], ";", "\[IndentingNewLine]", 
         RowBox[{"u", "=", 
          RowBox[{"Quotient", "[", 
           RowBox[{"t1", ",", 
            RowBox[{"dd", "[", 
             RowBox[{"[", "i", "]"}], "]"}]}], "]"}]}], ";"}]}], 
       "\[IndentingNewLine]", "]"}], ";", "\[IndentingNewLine]", 
      RowBox[{"If", "[", 
       RowBox[{
        RowBox[{"low", "<", "up"}], ",", 
        RowBox[{
         RowBox[{"lam", "[", 
          RowBox[{"[", 
           RowBox[{"up", ",", "low"}], "]"}], "]"}], "=", "u"}], ",", 
        RowBox[{
         RowBox[{"dd", "[", 
          RowBox[{"[", 
           RowBox[{"up", "+", "1"}], "]"}], "]"}], "=", "u"}]}], "]"}]}]}], 
    "\[IndentingNewLine]", "]"}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"SetAttributes", "[", 
    RowBox[{"reduce", ",", "HoldAll"}], "]"}], ";"}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"reduce", "[", 
   RowBox[{"k_", ",", "l_", ",", "dd_", ",", "lam_", ",", "uu_"}], "]"}], ":=",
   "\[IndentingNewLine]", 
  RowBox[{"Module", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"t1", ",", "t2", ",", "u", ",", "i"}], "}"}], ",", 
    RowBox[{"(*", " ", 
     RowBox[{
     "Subtract", " ", "multiple", " ", "of", " ", "row", " ", "l", " ", 
      "from", " ", "row", " ", 
      RowBox[{"k", "."}]}], " ", "*)"}], "\[IndentingNewLine]", 
    RowBox[{
     RowBox[{"t2", "=", 
      RowBox[{"dd", "[", 
       RowBox[{"[", 
        RowBox[{"l", "+", "1"}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"t1", "=", 
      RowBox[{"Abs", "[", 
       RowBox[{"2", " ", 
        RowBox[{"lam", "[", 
         RowBox[{"[", 
          RowBox[{"k", ",", "l"}], "]"}], "]"}]}], "]"}]}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"If", "[", 
      RowBox[{
       RowBox[{"t1", ">", "t2"}], ",", "\[IndentingNewLine]", 
       RowBox[{
        RowBox[{"u", "=", 
         RowBox[{"Quotient", "[", 
          RowBox[{
           RowBox[{
            RowBox[{"2", 
             RowBox[{"lam", "[", 
              RowBox[{"[", 
               RowBox[{"k", ",", "l"}], "]"}], "]"}]}], "+", "t2"}], ",", 
           RowBox[{"2", " ", "t2"}]}], "]"}]}], ";", "\[IndentingNewLine]", 
        RowBox[{
         RowBox[{"uu", "[", 
          RowBox[{"[", "k", "]"}], "]"}], "=", 
         RowBox[{
          RowBox[{"uu", "[", 
           RowBox[{"[", "k", "]"}], "]"}], "-", 
          RowBox[{"u", " ", 
           RowBox[{"uu", "[", 
            RowBox[{"[", "l", "]"}], "]"}]}]}]}], ";", "\[IndentingNewLine]", 
        
        RowBox[{
         RowBox[{"lam", "[", 
          RowBox[{"[", 
           RowBox[{"k", ",", "l"}], "]"}], "]"}], "=", 
         RowBox[{
          RowBox[{"lam", "[", 
           RowBox[{"[", 
            RowBox[{"k", ",", "l"}], "]"}], "]"}], "-", 
          RowBox[{"t2", " ", "u"}]}]}], ";", "\[IndentingNewLine]", 
        RowBox[{"For", "[", 
         RowBox[{
          RowBox[{"i", "=", "1"}], ",", 
          RowBox[{"i", "<", "l"}], ",", 
          RowBox[{"i", "++"}], ",", "\[IndentingNewLine]", 
          RowBox[{
           RowBox[{"lam", "[", 
            RowBox[{"[", 
             RowBox[{"k", ",", "i"}], "]"}], "]"}], "=", 
           RowBox[{
            RowBox[{"lam", "[", 
             RowBox[{"[", 
              RowBox[{"k", ",", "i"}], "]"}], "]"}], "-", 
            RowBox[{"u", " ", 
             RowBox[{"lam", "[", 
              RowBox[{"[", 
               RowBox[{"l", ",", "i"}], "]"}], "]"}]}]}]}]}], 
         "\[IndentingNewLine]", "]"}]}]}], "\[IndentingNewLine]", "]"}]}]}], 
   "\[IndentingNewLine]", "]"}]}]}], "Input",
 InitializationCell->True]
}, Open  ]],

Cell[CellGroupData[{

Cell["Examples", "Subsection"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"?", "hnfLLL"}]], "Input"],

Cell[BoxData[
 StyleBox["\<\"{newmatrix,rank}=hnfLLL[mat,symbol] gives a lower triangular \
Hermite Normal Form of the integral matrix mat, together with its \
rank.\\n\\nIt also assigns to symbol an optimized matrix trans so that \
trans.mat=newmatrix.\"\>", "MSG"]], "Print", "PrintUsage",
 CellChangeTimes->{3.451454365847045*^9},
 CellTags->"Info3451461565-7892240"]
}, Open  ]],

Cell[BoxData[
 RowBox[{
  RowBox[{"ma", "=", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"51", ",", "78", ",", 
       RowBox[{"-", "17"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "75"}], ",", 
       RowBox[{"-", "63"}], ",", "48"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "92"}], ",", "87", ",", 
       RowBox[{"-", "66"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "96"}], ",", "7", ",", "73"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"41", ",", "17", ",", "3"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "78"}], ",", "6", ",", "58"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"47", ",", 
       RowBox[{"-", "34"}], ",", 
       RowBox[{"-", "71"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"34", ",", "28", ",", 
       RowBox[{"-", "11"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"13", ",", 
       RowBox[{"-", "59"}], ",", 
       RowBox[{"-", "94"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"90", ",", 
       RowBox[{"-", "32"}], ",", 
       RowBox[{"-", "33"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"76", ",", 
       RowBox[{"-", "62"}], ",", "48"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "20"}], ",", "16", ",", 
       RowBox[{"-", "87"}]}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"2", ",", "92", ",", "29"}], "}"}], ",", 
     RowBox[{"{", 
      RowBox[{"14", ",", 
       RowBox[{"-", "89"}], ",", 
       RowBox[{"-", "32"}]}], "}"}]}], "}"}]}], ";"}]], "Input"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"hnf", "[", 
   RowBox[{"ma", ",", "uu"}], "]"}], ";", 
  RowBox[{"Max", "[", 
   RowBox[{"Abs", "[", "uu", "]"}], "]"}]}]], "Input"],

Cell[BoxData["1234483"], "Output",
 CellChangeTimes->{3.4514543660374537`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"hnfLLL", "[", 
   RowBox[{"ma", ",", "uuLLL"}], "]"}], ";", 
  RowBox[{"Max", "[", 
   RowBox[{"Abs", "[", "uuLLL", "]"}], "]"}]}]], "Input"],

Cell[BoxData["4"], "Output",
 CellChangeTimes->{3.451454366101996*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"uuLLL", ".", "ma"}], "\[Equal]", 
  RowBox[{"uu", ".", "ma"}]}]], "Input"],

Cell[BoxData["True"], "Output",
 CellChangeTimes->{3.4514543661563873`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Det", "[", "uuLLL", "]"}]], "Input"],

Cell[BoxData["1"], "Output",
 CellChangeTimes->{3.4514543662221107`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "ma", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"51", "78", 
      RowBox[{"-", "17"}]},
     {
      RowBox[{"-", "75"}], 
      RowBox[{"-", "63"}], "48"},
     {
      RowBox[{"-", "92"}], "87", 
      RowBox[{"-", "66"}]},
     {
      RowBox[{"-", "96"}], "7", "73"},
     {"41", "17", "3"},
     {
      RowBox[{"-", "78"}], "6", "58"},
     {"47", 
      RowBox[{"-", "34"}], 
      RowBox[{"-", "71"}]},
     {"34", "28", 
      RowBox[{"-", "11"}]},
     {"13", 
      RowBox[{"-", "59"}], 
      RowBox[{"-", "94"}]},
     {"90", 
      RowBox[{"-", "32"}], 
      RowBox[{"-", "33"}]},
     {"76", 
      RowBox[{"-", "62"}], "48"},
     {
      RowBox[{"-", "20"}], "16", 
      RowBox[{"-", "87"}]},
     {"2", "92", "29"},
     {"14", 
      RowBox[{"-", "89"}], 
      RowBox[{"-", "32"}]}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.451454366289535*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "uu", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {
      RowBox[{"-", "963267"}], 
      RowBox[{"-", "1234483"}], 
      RowBox[{"-", "72318"}], "522009", "0", "0", "0", "0", "0", "0", "0", 
      "0", "0", "0"},
     {
      RowBox[{"-", "614329"}], 
      RowBox[{"-", "787298"}], 
      RowBox[{"-", "46121"}], "332914", "1", "0", "0", "0", "0", "0", "0", 
      "0", "0", "0"},
     {
      RowBox[{"-", "21658"}], 
      RowBox[{"-", "27756"}], 
      RowBox[{"-", "1626"}], "11736", "0", "1", "0", "0", "0", "0", "0", "0", 
      "0", "0"},
     {
      RowBox[{"-", "721535"}], 
      RowBox[{"-", "924690"}], 
      RowBox[{"-", "54170"}], "391012", "0", "0", "1", "0", "0", "0", "0", 
      "0", "0", "0"},
     {
      RowBox[{"-", "266625"}], 
      RowBox[{"-", "341695"}], 
      RowBox[{"-", "20017"}], "144488", "0", "0", "0", "1", "0", "0", "0", 
      "0", "0", "0"},
     {
      RowBox[{"-", "102343"}], 
      RowBox[{"-", "131160"}], 
      RowBox[{"-", "7684"}], "55463", "0", "0", "0", "0", "1", "0", "0", "0", 
      "0", "0"},
     {
      RowBox[{"-", "49034"}], 
      RowBox[{"-", "62840"}], 
      RowBox[{"-", "3681"}], "26573", "0", "0", "0", "0", "0", "1", "0", "0", 
      "0", "0"},
     {
      RowBox[{"-", "212489"}], 
      RowBox[{"-", "272317"}], 
      RowBox[{"-", "15952"}], "115151", "0", "0", "0", "0", "0", "0", "1", 
      "0", "0", "0"},
     {
      RowBox[{"-", "32531"}], 
      RowBox[{"-", "41691"}], 
      RowBox[{"-", "2443"}], "17630", "0", "0", "0", "0", "0", "0", "0", "1", 
      "0", "0"},
     {
      RowBox[{"-", "421083"}], 
      RowBox[{"-", "539641"}], 
      RowBox[{"-", "31613"}], "228190", "0", "0", "0", "0", "0", "0", "0", 
      "0", "1", "0"},
     {
      RowBox[{"-", "272031"}], 
      RowBox[{"-", "348625"}], 
      RowBox[{"-", "20423"}], "147419", "0", "0", "0", "0", "0", "0", "0", 
      "0", "0", "1"},
     {
      RowBox[{"-", "441141"}], 
      RowBox[{"-", "565348"}], 
      RowBox[{"-", "33119"}], "239061", "0", "0", "0", "0", "0", "0", "0", 
      "0", "0", "0"},
     {
      RowBox[{"-", "603910"}], 
      RowBox[{"-", "773946"}], 
      RowBox[{"-", "45339"}], "327268", "0", "0", "0", "0", "0", "0", "0", 
      "0", "0", "0"},
     {
      RowBox[{"-", "297899"}], 
      RowBox[{"-", "381775"}], 
      RowBox[{"-", "22365"}], "161436", "0", "0", "0", "0", "0", "0", "0", 
      "0", "0", "0"}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.451454366341305*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"MatrixForm", "[", "uuLLL", "]"}]], "Input"],

Cell[BoxData[
 TagBox[
  RowBox[{"(", "\[NoBreak]", GridBox[{
     {"1", "1", 
      RowBox[{"-", "1"}], "1", "1", "0", "0", "2", "1", 
      RowBox[{"-", "1"}], "0", "1", "1", "1"},
     {"1", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], "1", 
      RowBox[{"-", "1"}], "0", "1", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], "0", 
      RowBox[{"-", "1"}], "1", "0", "2"},
     {
      RowBox[{"-", "2"}], 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], "0", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], 
      RowBox[{"-", "1"}], "1", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], "1", "1", "1"},
     {
      RowBox[{"-", "2"}], 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], "1", 
      RowBox[{"-", "2"}], "1", "0", "3", "1", "2", 
      RowBox[{"-", "1"}], "0", "0", 
      RowBox[{"-", "2"}]},
     {
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], "0", 
      RowBox[{"-", "2"}], "1", "2", "0", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "3"}], "0", "0", "2", 
      RowBox[{"-", "1"}], "1"},
     {"2", 
      RowBox[{"-", "1"}], "0", "0", "0", "2", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], "2", "1", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], "0", "1"},
     {
      RowBox[{"-", "1"}], "0", "0", 
      RowBox[{"-", "2"}], 
      RowBox[{"-", "4"}], "0", "0", "2", 
      RowBox[{"-", "3"}], "0", "0", "1", "0", "1"},
     {
      RowBox[{"-", "2"}], "2", "0", 
      RowBox[{"-", "1"}], "0", 
      RowBox[{"-", "1"}], "2", 
      RowBox[{"-", "2"}], "0", "1", "0", "0", "2", 
      RowBox[{"-", "3"}]},
     {"1", "0", "2", "0", "0", "2", 
      RowBox[{"-", "1"}], "1", 
      RowBox[{"-", "2"}], "4", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], "2"},
     {"0", "0", 
      RowBox[{"-", "1"}], "3", 
      RowBox[{"-", "2"}], 
      RowBox[{"-", "1"}], "0", "0", "0", "2", "1", "3", "2", "0"},
     {
      RowBox[{"-", "3"}], 
      RowBox[{"-", "1"}], "0", "1", "1", "0", "2", "1", "1", 
      RowBox[{"-", "1"}], "1", "0", "3", "0"},
     {"1", 
      RowBox[{"-", "1"}], "1", "0", "0", "2", 
      RowBox[{"-", "2"}], 
      RowBox[{"-", "1"}], "1", "2", "1", "0", 
      RowBox[{"-", "2"}], 
      RowBox[{"-", "1"}]},
     {"0", "0", "1", 
      RowBox[{"-", "2"}], "0", "1", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "2"}], "1", 
      RowBox[{"-", "1"}], "2", "0", "2", "1"},
     {
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], "2", 
      RowBox[{"-", "1"}], 
      RowBox[{"-", "1"}], "3", "0", "0", 
      RowBox[{"-", "1"}], "0", "0", "1", 
      RowBox[{"-", "1"}]}
    },
    GridBoxAlignment->{
     "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, 
      "RowsIndexed" -> {}},
    GridBoxSpacings->{"Columns" -> {
        Offset[0.27999999999999997`], {
         Offset[0.7]}, 
        Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
        Offset[0.2], {
         Offset[0.4]}, 
        Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}],
  Function[BoxForm`e$, 
   MatrixForm[BoxForm`e$]]]], "Output",
 CellChangeTimes->{3.45145436639089*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"ma", "=", 
  RowBox[{"mat", "[", 
   RowBox[{"1", ",", "18", ",", "100"}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{"-", "23"}], "}"}], ",", 
   RowBox[{"{", "54", "}"}], ",", 
   RowBox[{"{", "59", "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "75"}], "}"}], ",", 
   RowBox[{"{", "88", "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "97"}], "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "29"}], "}"}], ",", 
   RowBox[{"{", "98", "}"}], ",", 
   RowBox[{"{", "62", "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "49"}], "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "53"}], "}"}], ",", 
   RowBox[{"{", "95", "}"}], ",", 
   RowBox[{"{", "78", "}"}], ",", 
   RowBox[{"{", "20", "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "15"}], "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "17"}], "}"}], ",", 
   RowBox[{"{", 
    RowBox[{"-", "26"}], "}"}], ",", 
   RowBox[{"{", "63", "}"}]}], "}"}]], "Output",
 CellChangeTimes->{3.451454366460862*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"hnf", "[", 
  RowBox[{"ma", ",", "uu"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "1", "}"}]}], "}"}], ",", "1"}], "}"}]], "Output",
 CellChangeTimes->{3.451454366522327*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "uu", "]"}], "]"}]], "Input"],

Cell[BoxData["54"], "Output",
 CellChangeTimes->{3.451454366586464*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"hnfLLL", "[", 
  RowBox[{"ma", ",", "uuLLL"}], "]"}]], "Input"],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "0", "}"}], ",", 
     RowBox[{"{", "1", "}"}]}], "}"}], ",", "1"}], "}"}]], "Output",
 CellChangeTimes->{3.451454366750675*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"Max", "[", 
  RowBox[{"Abs", "[", "uuLLL", "]"}], "]"}]], "Input"],

Cell[BoxData["1"], "Output",
 CellChangeTimes->{3.451454366788336*^9}]
}, Open  ]]
}, Open  ]]
}, Closed]]
},
AutoGeneratedPackage->Automatic,
WindowSize->{1568, 904},
WindowMargins->{{0, Automatic}, {Automatic, 0}},
ShowSelection->True,
Magnification->1.25,
FrontEndVersion->"7.0 for Mac OS X x86 (32-bit) (November 10, 2008)",
StyleDefinitions->"Classroom.nb"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{
 "Info3451461559-9264477"->{
  Cell[19536, 512, 384, 6, 90, "Print",
   CellTags->"Info3451461559-9264477"]},
 "Info3451461565-7892240"->{
  Cell[57172, 1656, 370, 6, 90, "Print",
   CellTags->"Info3451461565-7892240"]}
 }
*)
(*CellTagsIndex
CellTagsIndex->{
 {"Info3451461559-9264477", 71646, 2162},
 {"Info3451461565-7892240", 71756, 2165}
 }
*)
(*NotebookFileOutline
Notebook[{
Cell[545, 20, 143, 3, 118, "Title"],
Cell[691, 25, 2585, 46, 425, "Text"],
Cell[CellGroupData[{
Cell[3301, 75, 31, 0, 63, "Section"],
Cell[3335, 77, 9481, 235, 1101, "Input",
 InitializationCell->True],
Cell[12819, 314, 6579, 186, 512, "Input",
 InitializationCell->True]
}, Closed]],
Cell[CellGroupData[{
Cell[19435, 505, 27, 0, 37, "Section"],
Cell[CellGroupData[{
Cell[19487, 509, 46, 1, 55, "Input"],
Cell[19536, 512, 384, 6, 90, "Print",
 CellTags->"Info3451461559-9264477"]
}, Open  ]],
Cell[19935, 521, 1437, 39, 113, "Input"],
Cell[21375, 562, 178, 6, 55, "Input"],
Cell[CellGroupData[{
Cell[21578, 572, 82, 2, 55, "Input"],
Cell[21663, 576, 73, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[21773, 582, 142, 4, 55, "Input"],
Cell[21918, 588, 73, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[22028, 594, 64, 1, 55, "Input"],
Cell[22095, 597, 1481, 43, 167, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[23613, 645, 65, 1, 55, "Input"],
Cell[23681, 648, 964, 25, 167, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[24682, 678, 63, 1, 55, "Input"],
Cell[24748, 681, 1489, 40, 167, "Output"]
}, Open  ]],
Cell[26252, 724, 476, 11, 193, "Text"],
Cell[CellGroupData[{
Cell[26753, 739, 189, 6, 55, "Input"],
Cell[26945, 747, 832, 25, 167, "Output"]
}, Open  ]],
Cell[27792, 775, 153, 4, 29, "Text"],
Cell[CellGroupData[{
Cell[27970, 783, 515, 16, 55, "Input"],
Cell[28488, 801, 73, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[28598, 807, 64, 1, 55, "Input"],
Cell[28665, 810, 1481, 43, 167, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[30183, 858, 65, 1, 55, "Input"],
Cell[30251, 861, 1133, 30, 167, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[31421, 896, 63, 1, 55, "Input"],
Cell[31487, 899, 1414, 34, 167, "Output"]
}, Open  ]],
Cell[32916, 936, 61, 1, 29, "Text"],
Cell[32980, 939, 430, 14, 55, "Input",
 InitializationCell->True],
Cell[33413, 955, 179, 4, 29, "Text"],
Cell[33595, 961, 284, 10, 55, "Input"],
Cell[CellGroupData[{
Cell[33904, 975, 88, 2, 55, "Input"],
Cell[33995, 979, 210, 3, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[34242, 987, 86, 2, 55, "Input"],
Cell[34331, 991, 204, 3, 71, "Output"]
}, Open  ]],
Cell[34550, 997, 84, 1, 29, "Text"],
Cell[34637, 1000, 284, 10, 55, "Input"],
Cell[CellGroupData[{
Cell[34946, 1014, 88, 2, 55, "Input"],
Cell[35037, 1018, 70, 1, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[35144, 1024, 86, 2, 55, "Input"],
Cell[35233, 1028, 210, 3, 70, "Output"]
}, Open  ]],
Cell[35458, 1034, 314, 6, 50, "Text"],
Cell[CellGroupData[{
Cell[35797, 1044, 115, 3, 55, "Input"],
Cell[35915, 1049, 89, 1, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[36041, 1055, 116, 3, 55, "Input"],
Cell[36160, 1060, 86, 1, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[36283, 1066, 232, 7, 55, "Input"],
Cell[36518, 1075, 87, 1, 70, "Output"]
}, Open  ]],
Cell[36620, 1079, 204, 5, 29, "Text"],
Cell[36827, 1086, 6542, 174, 531, "Input"],
Cell[43372, 1262, 62, 1, 29, "Text"],
Cell[43437, 1265, 290, 10, 55, "Input"],
Cell[CellGroupData[{
Cell[43752, 1279, 88, 2, 55, "Input"],
Cell[43843, 1283, 249, 4, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[44129, 1292, 86, 2, 55, "Input"],
Cell[44218, 1296, 882, 12, 70, "Output"]
}, Open  ]],
Cell[45115, 1311, 48, 1, 29, "Text"],
Cell[45166, 1314, 178, 6, 55, "Input"],
Cell[CellGroupData[{
Cell[45369, 1324, 88, 2, 55, "Input"],
Cell[45460, 1328, 70, 1, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[45567, 1334, 86, 2, 55, "Input"],
Cell[45656, 1338, 102, 1, 70, "Output"]
}, Open  ]],
Cell[45773, 1342, 74, 1, 29, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[45884, 1348, 50, 0, 37, "Section"],
Cell[45937, 1350, 520, 11, 71, "Text"],
Cell[CellGroupData[{
Cell[46482, 1365, 37, 0, 51, "Subsection"],
Cell[46522, 1367, 10506, 277, 1063, "Input",
 InitializationCell->True]
}, Open  ]],
Cell[CellGroupData[{
Cell[57065, 1649, 30, 0, 51, "Subsection"],
Cell[CellGroupData[{
Cell[57120, 1653, 49, 1, 55, "Input"],
Cell[57172, 1656, 370, 6, 90, "Print",
 CellTags->"Info3451461565-7892240"]
}, Open  ]],
Cell[57557, 1665, 1594, 51, 75, "Input"],
Cell[CellGroupData[{
Cell[59176, 1720, 167, 5, 55, "Input"],
Cell[59346, 1727, 78, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[59461, 1733, 176, 5, 55, "Input"],
Cell[59640, 1740, 70, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[59747, 1746, 109, 3, 55, "Input"],
Cell[59859, 1751, 75, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[59971, 1757, 60, 1, 55, "Input"],
Cell[60034, 1760, 72, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[60143, 1766, 64, 1, 55, "Input"],
Cell[60210, 1769, 1357, 49, 319, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[61604, 1823, 64, 1, 55, "Input"],
Cell[61671, 1826, 2946, 86, 319, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[64654, 1917, 67, 1, 55, "Input"],
Cell[64724, 1920, 3210, 100, 319, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[67971, 2025, 117, 3, 55, "Input"],
Cell[68091, 2030, 905, 30, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[69033, 2065, 81, 2, 55, "Input"],
Cell[69117, 2069, 792, 23, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[69946, 2097, 87, 2, 55, "Input"],
Cell[70036, 2101, 71, 1, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[70144, 2107, 87, 2, 55, "Input"],
Cell[70234, 2111, 792, 23, 71, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[71063, 2139, 90, 2, 55, "Input"],
Cell[71156, 2143, 70, 1, 71, "Output"]
}, Open  ]]
}, Open  ]]
}, Closed]]
}
]
*)

(* End of internal cache information *)