Sharedwww / talks / 2005-09-15-sandpyt-sage / pycon-sage.texOpen in CoCalc
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\\
39
Assoc. 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
64
SAGE is a {\em Python} framework for number theory, algebra, and
65
geometry computation. It is open source and freely available under
66
the 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
79
\item Design influenced by the non-free computer algebra program
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
149
to Fermat's last theorem, distribution of primes (the Riemann
150
Hypothesis), 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.)
169
Means 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
208
number 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}
221
I am creating a system using Python that will hopefully solve the
222
problem. I've been working on this for 8 months (and I've been
223
writing number theory software since 1998, in C++ and MAGMA). Please
224
download and try it, though it is still {\em not ready} for prime
225
time:
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
236
to C code from Python, and compiled).
237
Wrapping C++ libraries by wrapping in C and using Pyrex (avoid
238
SWIG 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}
253
Asside from being open source, building SAGE
254
using 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
282
Everybody 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
297
pre-parser for IPython so that the command line behavior of IPython is
298
what one expects in mathematics, e.g., typing {\tt a = 2/3}
299
will 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
301
standard Python rules when writing code in a file. This was
302
easy 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