CoCalc Public Fileswww / talks / 2005-09-15-sandpyt-sage / pycon-sage.tex
Author: William A. Stein
1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%  (c) 2005,
3%    William Stein
4%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
5
6\documentclass[landscape]{slides}
7\newcommand{\page}[1]{\begin{slide}#1\vfill\end{slide}}
8%\renewcommand{\page}[1]{}
9\newcommand{\apage}[1]{\begin{slide}#1\vfill\end{slide}}
10
11\newcommand{\eps}[4]{\rput[lb](#1,#2){%
12    \includegraphics[width=#3\textwidth]{#4}}}
13
14\usepackage{fullpage}
15\usepackage{amsmath}
16\usepackage{amsfonts}
17\usepackage{amssymb}
18\usepackage{amsthm}
19\usepackage{graphicx}
20\theoremstyle{plain}
21\newtheorem{theorem}{Theorem}
22\newtheorem{proposition}[theorem]{Proposition}
23\newtheorem{corollary}[theorem]{Corollary}
24\newtheorem{claim}[theorem]{Claim}
25\newtheorem{lemma}[theorem]{Lemma}
26\newtheorem{conjecture}[theorem]{Conjecture}
27\usepackage{pstricks}
28\newrgbcolor{dbluecolor}{0 0 0.6}
29\newrgbcolor{dredcolor}{0.5 0 0}
30\newrgbcolor{dgreencolor}{0 0.4 0}
31\newcommand{\dred}{\dredcolor\bf}
32\newcommand{\dblue}{\dbluecolor\bf}
33\newcommand{\dgreen}{\dgreencolor\bf}
34
35
36\title{\bf\dred SAGE: System for Algebra and Geometry Experimentation\\
37{\tt http://modular.ucsd.edu/sage/}}
38\author{\large William Stein\\
39Assoc. Professor of Mathematics, UCSD}
40\date{Sept 15, 2005, SANDPYT\\
41}
42
43\bibliographystyle{amsalpha}
44\newcommand{\section}[1]{\begin{center}{\dblue \bf\Large #1}\end{center}}
45\newcommand{\Q}{\mathbb{Q}}
46\newcommand{\Z}{\mathbb{Z}}
47\newcommand{\defn}[1]{{\em #1}}
48\renewcommand{\H}{\HH}
49\newcommand{\hra}{\hookrightarrow}
50\newcommand{\isom}{\cong}
51\newcommand{\ds}{\displaystyle}
52
53
54\begin{document}
55\small
56
57\page{
58\maketitle
59}
60
61\page{
62\section{What is SAGE?}
63\vfill
64SAGE is a {\em Python} framework for number theory, algebra, and
65geometry computation.  It is open source and freely available under
66the terms of the GNU General Public License (GPL).
67\vfill
68\begin{itemize}
69\item Mainly written by William Stein (other contributors include
70  David Joyner, David Kohel, Kyle Schalm, Justin Walker, etc.)
71
72\item SAGE is a Python library with a customized interpreter.  It is
73  written in Python, C++, C, and Pyrex.  ({\bf No} use of SWIG or psycho.)
74
75\item Interface to open source libraries for computing with elliptic
76  curves (mwrank), number theory (PARI, NTL), commutative algebra
77  (Singular), and group theory (GAP).  Not finished.
78
80  MAGMA. Focuses on a class structure that reflects the mathematical
81  objects that mathematicians think about, rather than symbolic
82  manipulation.
83
84\end{itemize}
85
86}
87
88\begin{slide}
89\section{SAGE in Action}
90{\tiny
91\vfill
92\begin{verbatim}
93    $sage 94 ------------------------------------------------------------------------ 95 SAGE Version 0.6.beta2, Export Date: 2005-09-08-1814 96 Distributed under the terms of the GNU General Public License (GPL) 97 IPython shell -- for help type <object>?, <object>??, %magic, or help 98 ------------------------------------------------------------------------ 99 100 sage: p = next_prime(10^15) 101 sage: p 102 _2 = 1000000000000037 103 sage: q = next_prime(10^17) 104 sage: n = p*q 105 sage: factor(n) 106 _5 = [(1000000000000037, 1), (100000000000000003, 1)] 107 sage: a = 1/3 108 sage: a 109 _7 = 1/3 110 sage: type(a) 111 _8 = <type '_rational.Rational'> 112 sage: a.parent() 113 _9 = Rational Field 114 sage: Q = _ 115 sage: R = PolynomialRing(Q, 'a'); a = R.gen(0) 116 sage: f = a^2 +a + 1 117 sage: f^3 118 _13 = a^6 + 3*a^5 + 6*a^4 + 7*a^3 + 6*a^2 + 3*a + 1 119 sage: parent(f) 120 _14 = Univariate Polynomial Ring in a over Rational Field 121 sage: S = R.quotient(f, 'b'); b = S.0 122 sage: S 123 _17 = Univariate Quotient Polynomial Ring in b over 124 Rational Field with modulus a^2 + a + 1 125 sage: b+1 126 _18 = b + 1 127 sage: b^2 128 _19 = -b - 1 129 sage: V = VectorSpace(Q,4) 130 sage: V 131 _21 = Full Vector space of degree 4 over Rational Field 132 sage: V.random_element() 133 _22 = (1, 1, 1, 1) 134 sage: k = GF(23^2, 'a'); a = k.0 135 sage: k 136 _28 = Finite field of size 23^2 137 sage: a^5 138 _26 = 4*a + 14 139\end{verbatim} 140\end{slide} 141 142 143\page{ 144\section{Target Audience} 145\vfill 146{\large 147\begin{itemize} 148\item {\dblue Number theorists:} people who study problems related 149to Fermat's last theorem, distribution of primes (the Riemann 150Hypothesis), arithmetic of elliptic curves, etc. 151 152\item {\dblue Cryptography researchers:} people who improve understanding of 153 cryptosystems. Most software for crypto is non-free, for obvious 154 reasons. 155\end{itemize} 156} 157} 158 159\page{ 160\section{Main Goals} 161 162\vfill 163\begin{itemize} 164 165\item {\dblue Efficient:} Be very fast -- comparable to other systems. 166 {\bf Very} difficult, since most systems are closed source, 167 algorithms are often not published, and finding fast algorithms is 168 often extremely difficult (years of work, Ph.D. theses, luck, etc.) 169Means much non pure Python code. 170 171\item {\dblue Free and Open Source:} The source code must be available 172 and readable, so users can understand what the system is really 173 doing. Math research papers are easier to verify, extend and use 174 when they rely only on free open software. 175 176\item {\dblue Well documented:} Reference manual and an API reference 177 with example usage for every function. Make documentation and 178 source a peer reviewed package, so get academic credit like a 179 journal publication. 180 181\end{itemize} 182} 183 184 185\page{ 186\section{Existing Mature Systems} 187\begin{itemize} 188\item {\dblue Mathematica, Maple, and MATLAB:} Number theory / 189 cryptograhy is not the target audience. Mathematica does well at 190 special functions, and both do calculus very well. These systems 191 are {\em closed source, expensive, for profit}. 192 193% 194 195\item {\dblue MAGMA:} {\em By far} the best software for number theory 196 and cryptography research. It's efficient, comprehensive, and well 197 documented. Great design (but could be better). BUT: It's closed 198 source (but non-profit), expensive, and not easily extensible ({\em no 199 user defined types or C/C++-extension code}). I've contributed 200 substantially to MAGMA. 201 202\item {\dblue PARI:} Efficient, open source, extendible and free. But 203 the documentation is not good enough and the memory management is 204 not robust enough. Also, PARI does not do nearly as much as what is 205 needed. 206 207\item {\dblue Maxima, Octave, etc.:} Open source, but not for 208number theory. 209 210%\item {\dblue NZMATH:} Number theory in pure Python. Different 211%goals. 212 213\end{itemize} 214(There's always something else that I don't know about.) 215 216{\em {\bf All} these system use their own custom programming language.} 217} % end page 218 219\page{ 220\section{SAGE: System for Algebra and Geometry Experimentation} 221I am creating a system using Python that will hopefully solve the 222problem. I've been working on this for 8 months (and I've been 223writing number theory software since 1998, in C++ and MAGMA). Please 224download and try it, though it is still {\em not ready} for prime 225time: 226\begin{center} 227{\tt http://modular.ucsd.edu/sage}. 228\end{center} 229\begin{itemize} 230 231\item {\em SciPy/Numarray-ish:} but for number theory. 232 233\item {\dblue Financial Support:} NSF Grant DMS-0400386. 234 235\item {\dblue Implementation:} C/C++, Python, and Pyrex (easy access 236to C code from Python, and compiled). 237Wrapping C++ libraries by wrapping in C and using Pyrex (avoid 238SWIG for simplicity and performance). 239 240 241\item {\dblue Libraries:} GMP, MPFR, PARI, mwrank, NTL, etc. These 242 are all are GPL'd and SAGE provides (or will provide) a unified 243 interface for using them. Not reinventing wheel. 244 245\item {\dblue Current Platforms:} Linux, OS X, and Windows. 246 Architecture independent, so {\em no use of psyco}. 247 248\end{itemize} 249} % end page 250 251\page{ 252\section{Advantages to Using Python} 253Asside from being open source, building SAGE 254using Python has several advantages. 255\begin{itemize} 256\item {\dred Object persistence} is easy in Python---but 257 difficult in many other math systems. 258 259% \item That function arguments can be of any type is extremely 260%important in writing mathematics code. E.g., a generic echelon 261%for matrices over {\em any field} is straightforward to write. 262 263\item Good support for {\dred doctest} and automatic extraction of API 264 documentation from docstrings. Having lots of examples that are 265 tested and guaranteed to work as indicated. 266 267\item {\dred Memory management}: Python deals well with {\dred circular 268 references}. 269 270\item Python has {\dred many packages} available now that may prove 271 useful in number theory/crypto research: numarray/Numeric/SciPy, 2d 272 and 3d graphics, networking (for distributed computation), etc. 273 274\item Easy to {\dred compile} Python on many platforms. 275 276\end{itemize} 277} 278 279\begin{slide} 280\section{Standard Python Math Annoyances} 281\vfill 282Everybody who does mathematics using Python runs into these problems: 283\vfill 284\begin{itemize} 285 \item \verb|**| versus \verb|^| -- easy for me 286 to get used to, but must define \verb|^| to give 287 an error on any arithmetic SAGE type. (In IPython shell lines can 288 be pre-parsed, so this can be solved nicely.) 289 290 \item \verb|sin(2/3)| has {\em much} different behavior in Python than 291 in any standard math system. 292 293\end{itemize} 294\vfill 295 296{\bf Solution:} Leave the Python language exactly as is, and write a 297pre-parser for IPython so that the command line behavior of IPython is 298what one expects in mathematics, e.g., typing {\tt a = 2/3} 299will create {\tt a} as an exact rational number, and typing {\tt a = 300 3\verb|^|4} will set {\tt a} to 81. One must still obey the 301standard Python rules when writing code in a file. This was 302easy to do using IPython. 303 304\vfill\end{slide} 305 306\begin{slide} 307\section{More Examples} 308{\tiny 309\begin{verbatim} 310$ sage
311    sage: Q
312         Rational Field
313    sage: a = Q("2/3")
314    sage: a
315         2/3
316    sage: a in Q
317         True
318    sage: type(a)
319         <type 'rational.Rational'>
320    sage: 3^4    # illustration of IPython hack!
321         81
322    sage: 3\^4   # usual Python behavior (xor)
323         7
324\end{verbatim}}
325
326
327{\bf Create a matrix as an element of a space of matrices.}
328{\tiny
329\begin{verbatim}
330    sage: M = MatrixSpace(Q,3)
331    sage: M
332    Full MatrixSpace of 3 by 3 dense matrices over Rational Field
333    sage: B = M.basis()
334    sage: len(B)
335    9
336    sage: B[1]
337    [0 1 0]
338    [0 0 0]
339    [0 0 0]
340    sage: A = M(range(9)); A
341    [0 1 2]
342    [3 4 5]
343    [6 7 8]
344    sage: A.reduced_row_echelon_form()
345    [ 1  0 -1]
346    [ 0  1  2]
347    [ 0  0  0]
348    sage: A^20
349    [ 2466392619654627540480  3181394780427730516992  3896396941200833493504] ...
350    sage: A.kernel()
351    Vector space of degree 3, dimension 1 over Rational Field
352    Basis matrix:
353    [ 1 -2  1]
354    sage: kernel(A)   # functional notation, like in MAGMA
355\end{verbatim}
356}
357
358
359{\bf Compute with an elliptic curve.}
360{\tiny
361\begin{verbatim}
362    sage: E = EllipticCurve([0,0,1,-1,0])
363    sage: E
364         y^2 + y = x^3 - x
365    sage: P = E([0,0])
366    sage: 10*P
367         (161/16, -2065/64)
368    sage: 20*P
369         (683916417/264517696, -18784454671297/4302115807744)
370    sage: E.conductor()
371         37
372    sage: print E.anlist(30)    # coefficients of associated modular form
373        [0, 1, -2, -3, 2, -2, 6, -1, 0, 6, 4, -5, -6, -2, 2, 6, -4, 0, -12,
374         0, -4, 3, 10, 2, 0, -1, 4, -9, -2, 6, -12]
375    sage: M = ModularSymbols(37)
376    sage: D = M.decomposition()
377    sage: D
378    [Subspace of Modular Symbols of dimension 1 and level 37,
379     Subspace of Modular Symbols of dimension 2 and level 37,
380     Subspace of Modular Symbols of dimension 2 and level 37]
381    sage: D[1].T(2)
382    Linear function defined by matrix:
383    [0 0]
384    [0 0]
385    sage: D[2].T(2)
386    Linear function defined by matrix:
387    [-2  0]
388    [ 0 -2]
389\end{verbatim}
390}
391
392\end{slide}
393
394
395\end{document}
396
397