CS 487/687: Advanced Symbolic Computation

Introduction to Symbolic Computation

Introductory Maple Tutorial

Outline

  1. Getting Started: Interactive Maple
  2. Maple Programming
  3. Data Structures
  4. Number Theory
  5. Polynomials
  6. Linear Algebra
  7. Where to Get Help
  8. Appendix: Useful Maple Commands

This quick overview should get you started with the tools you'll need to use Maple effectively in this class. Many of you have probably used Maple in a calculus class to compute derivatives, integrals, and the like. Note that we will probably not be concentrating on such uses for this class, but rather writing more complicated programs in Maple, where each step is relatively simple so that we have a thorough understanding of what we are doing.

Note that we can't hope to cover every aspect of Maple programming, so you are encouraged to make use of Maple's help pages (in the program and online), as well as the course newsgroup, to answer any further questions you might have.

  1. Getting Started: Interactive Maple
    1. To GUI or not to GUI?
    2. There are two ways to run Maple: with the pretty interface (command xmaple), and without it. The GUI is (probably) more intuitive to use, but can also create complications. It will also be difficult for you to use if you don't have a personal copy of Maple. So we'll just be using the command line version by default.

      To run command line Maple, just type maple from the prompt of any of the "cpu" machines (e.g. cpu02.student.cs.uwaterloo.ca for undergrads, cpu102.cs.uwaterloo.ca for grads). Typing maple -h will give a list of all the command-line switches; the only one I find useful (sometimes) is -q.

    3. The Basics
    4. Maple code is a series of expressions. Each expression must be explicitly terminated with a semicolon ; (using a colon : instead suppresses output). Expressions will only be evaluated or simplified to a certain point automatically; further simplifications must be explicitly asked for.

      Variables like x, f, a, bar, etc. are simply symbols by default. They can also be assigned values with the := operator. Similar to functional programming languages like Scheme or Lisp, variables have no type, so they can refer to any expression (symbols, numbers, matrices, procedures...). However, every expression in Maple does have a type; check it with the whattype command.

      By default, all the simplifications Maple does are exact and symbolic. Rational, complex, and algebraic numbers are all supported. To find an approximation, use evalf (probably won't be used in this class). To evaluate an expression, substituting a specific value for one variable, use eval.

    5. Other Miscellany
    6. Sometimes a group of functions is grouped into a package or module. To access these, you can use the long form of the command, such as LinearAlgebra[CharacteristicPolynomial], or use the with command, as in with(LinearAlgebra), to lift those functions to the top namespace.

      When you're running big computations, you can prevent those pesky "bytes used" messages with kernelopts(printbytes=false). For timing your programs, use the time() command to get the total CPU time used so far in the execution.

  2. Maple Programming
    1. Programming Environment
    2. For this course, we'll be asking you to write your Maple programs in plaintext. You can use any text editor you like; some good ones like VIM or Emacs might even recognize Maple syntax. You can write any Maple expressions (such as procedure definitions) into your program file, and then read it into the interactive Maple session with read. Alternatively, you can pass in your file on the command line with a statement such as maple -q < myprogram.mpl.

    3. Maple Procedures
    4. A procedure in Maple is written with as proc(arg1,arg2,...) <expressions> end proc. Unlike the interactive Maple session, every variable you use must be declared either as an argument or a local or global variable (with the local and global keywords, respectively). These variable declarations should come first in your program; you probably won't use global as often as local.

      The value returned from your procedure will either be the last statement that gets executed, or the explicit value passed with a return statement.

    5. Ifs and Loops
    6. Maple supports if/then/else and while/for loops. The basic structure of each of these is as follows (type e.g. ?if for more information):

      if <condition> then <expressions> fi;
      for <var> from <start> to <end> do <expressions> od;
      while <condition> do <expressions> od;

    7. An Example
    8. Here's a procedure that takes an integer n and a number k, and determines whether n can be expressed as the sum of 2 positive k'th powers, and if so returns them.

      # Tells whether n can be expressed as a sum of 2 positive k'th powers,
      # and if so computes and returns them.
      sumKthPows := proc(n,k)
          local a1,a2,success;
          a1 := 0;
          while a1^k <= n/2 do
              a2 := iroot(n-a1^k, k, 'success');
              if success then
                  return a1,a2;
              fi;
              a1 := a1 + 1;
          od;
          return false;
      end proc;

      Some things to note:

      • sumKthPows is the name of the procedure, and we'll call it by writing e.g. sumKthPows(5,2). Since a procedure definition is an expression, we assign it just like anything else.
      • #'s are used for comments.
      • We don't usually need parentheses around conditions, etc. as in C.
      • Whitespace doesn't matter, but proper indentation makes it easy to read.
      • We can return multiple values (more on this in the next section).
      • iroot is a built-in Maple function. The optional third argument ('success' here) is an unevaluated name (more on this under "Number Theory").

    9. More Programming Stuff
    10. Maple is an interpreted language, so we can do fun things like write recursive programs, programs that return programs, etc., all though these are not necessarily recommended as they will probably be slow.

      Programs can take an arbitrary number of arguments, assign default values, etc., which can sometimes be useful. See the help pages under ?parameter for more details.

      print statements (and their variants) can be quite handy when writing procedures, especially ones that can take a long time.

  3. Data Structures
    1. Expression trees
    2. Any expression that doesn't get completely evaluated to a numbre or some other type of value is actually stored in a linked list, with a single operator describing how the list elements are to be combined.

      You can get at this by experimenting with whattype, nops, and op. For example, the expression 5*x + 20^n + 3 is of type "+" with three ops: 5*x (of type *), 20^n (of type ^), and 3 (of type integer).

    3. Sequences
    4. Some basic data structures provided by Maple can be very useful. First, a sequence is just a series of expressions, separated by commas. This is, for example, what we returned from the sumKthPows procedure above, in the case of success.

      The seq command makes it easy to create most kinds of sequences which can be indexed. For example, we can write the first 50 perfect squares as seq(i^2,i=1..50). Here note the range notation 1..50 (in general a..b) which is very common in Maple.

    5. Lists and Sets
    6. A list and a set in Maple are pretty much exactly what we would expect them to be: a list of expressions, and a group of distinct expressions, respectively. A list is formed by putting [...] around a sequence, and a set is formed by putting {,,,} around a sequence. Lists are especially useful as grouping a sequence into a single expression, which can then be passed to functions and handled with greater ease.

      We can access the i'th element (starting from 1) of a list or set A with A[i]. To convert a list or set back to a plain sequence, use empty brackets, e.g. A[].

  4. Number Theory
    1. Basic Integer Computations
    2. Most of the basic integer computations such as gcd, lcm, etc. are built-in Maple commands listed in the appendix of this document. We'll talk about how to use one here: igcdex (stands for extended GCD over integers).

      The format of this function call is igcdex(a, b, 's', 't'), where the last two arguments are optional. The return value is the actual greatest common divisor of a and b. The optional arguments 's' and 't' are unevaluated names (that's what the quotes are for), and the variables with those names will then be set to the multipliers computed in the Extended Euclidean Scheme. There are quite a few Maple functions that look like this; one we saw above is iroot, which takes an optional third argument which will be set to true or false depending on whether the computed root is exact.

      Note that igcdex is the preferred way to compute inverses mod a prime p. Can you think of how?

    3. Prime Numbers
    4. A few functions on prime numbers will be very useful to us. isprime performs a probabilistic test (which we can just assume works all of the time) to determine whether the given integer is prime. nextprime and prevprime compute the next integer greater than (resp. less than) the given one which is a prime number. These are especially useful when iterating loops over all prime numbers in some range, for example.

    5. Factorization
    6. Maple can also factor integers. Of course, we know that there's no known polynomial-time method to do this, so don't expect these methods to be very fast. ifactor does what you would expect; all prime factors and their multiplicities are returned. The similarly-named ifactors is much more useful when programming; it returns a list of lists with a very specific and well-defined form. Other related functions are isqrfree, numtheory[issqrfree], iroot, etc.

    7. Modular Arithmetic
    8. Very often we will perform computations over some small finite field (i.e. mod a prime) instead of over the integers, to avoid intermediate expression swell and greatly speed up computations. The tools to do this are scattered throughout Maple, but the standard ones are mod, modp, and mods. mod is used e.g. as in 12 mod 7 in the natural way we would generally write it. modp and mods are function calls; the difference is the range. modp(a,p) returns the unique integer congruent to a modulo p in the range 0..p-1, whereas mods(a,p) returns the image in the range -(p-1)/2..(p+1)/2 (here I'm assuming p is an odd prime).

      Actually, the behaviour of mod can be set to either modp or mods with a statement such as `mod` := mods (here the accent quotes must be used). The default behaviour is modp.

      Many "inert forms" of functions exist which expect to be followed by a mod. For example, there is an equivalent to the eval function, called Eval, which performs evaluation mod a prime. Note that using this form: Eval(f,x=1) mod p is much faster than doing eval(f,x=1) mod p; although they both return the same final result, the first form will be reducing modulo p at each step, greatly increasing the efficiency of the computation.

  5. Polynomials
    1. Representation and Access
    2. Polynomials are simply stored in Maple as ordinary expression trees; what makes them polynomials is their mathematical structure. Note that our polynomials can be in any variable or variables, so many of the functions on polynomials will take an argument (usually called x), which is the indeterminate we want the function to work over. The useful function indets will return a set of all the indeterminates in the given expression.

      The degree function returns (as we would expect) the degree of the given polynomial. Note that polynomials are by default stored in the sparse representation where only the nonzero terms are written down, We can get all the coefficients of a polynomial with the coeffs command. Note that these will be returned in no particular order. You can pass an optional argument to get a list of the monomial corresponding to the coefficients. For greater control, try the CoefficientVector command in the PolynomialTools package. It might also be convenient to use the sort function, which makes sure the terms of a polynomial are printed in order.

    3. Arithmetic
    4. Basic arithmetic can be performed with the normal operators +, -, *, etc. However, note that products and powers are not expanded by default; to force this, use the expand command. For multivariate polynomials, it might be convenient to treat the polynomial as univariate with coefficients in the other indeterminates; for this, collect can be used.

      The functions gcd, lcm, gcdex, etc. correspond to the normal integer functions, but now working over polynomials. Even more useful will be the inert forms Gcd, Lcm, etc., which again expect a mod to follow. For example, to find the gcd of polynomials f and g in x over the field Z7[x], write Gcd(f,g,x) mod 7.

    5. Polynomial Factorization
    6. Many tools are available to factor polynomials. The functions factor, irreduc, roots, and sqrfree all have intert forms (with a capital letter) as well. Note that polynomial factorization actually can be performed in polynomial time, although some of these routines will take some time.

    7. Efficient Modular Computation
    8. To compute much more efficiently with dense univariate polynomials over a finite field, we will use modp1. This works similarly to modp and mods on the surface, but actually it is doing much more. In fact, a whole different representation is used in this case. To convert to and from this, use the ConvertIn and ConvertOut functions.

      The modp1 function takes any one of the polynomial operations we've mentioned (and more) in their inert form (i.e. with a capital letter), and a modulus. So, for example, to compute the GCD of f and g as above over Z7[x] even more efficiently, write modp1(ConvertIn(f,x),ConvertIn(g,x),7). (Of course, the conversion takes some time, so it's best not to keep going back and forth).

  6. Linear Algebra
    1. Representation and Access
    2. Matrices have gone through a few historical eras in Maple. We will be using the current preferred representation, from the LinearAlgebra package. Note that this is not the same as the old linalg package. Our matrices and vectors will be of type Matrix and Vector resp., not matrix and vector. This is important.

      When you type with(LinearAlgebra);, you'll see a whole mess of routines that are getting imported into the namespace. Most of the routines you'll want to use come from these; the most useful ones are listed below.

      To create a Matrix or a Vector, you can use the functions Matrix and Vector, which give many options for instantiating the structures. For small, fixed Matrices and Vectors, you can use the shortcuts <...>, with , separating the entries of a column vector, and | separating the entries of a row vector. A Matrix is just a row vector of column vectors, or a column vector of row vectors. For example, the code <<1,2>|<3,4>|<5,6>> produces the matrix

      [1    3    5]
      [           ]
      [2    4    6]

      To access the entries of a Matrix or Vector, use the subscript brackets [] just as with lists or sets. Of course, Matrices will need two indices. Note that the entries of a Matrix by default are indexed in row-major order; that is, the first index selects the row, and the second index selects the column within that row. And again the indices start at 1. You can get the dimensions with the Dimensions command.

    3. Arithmetic
    4. The functions for arithmetic on Matrices and Vectors are all in the LinearAlgebra package; type ?LinearAlgebra or with(LinearAlgebra); to see a listing of them. Note that this includes basic arithmetic such as Multiply and Add, as well as matrix invariant computations such as Determinant and Rank. Another computation that will be useful is LinearSolve, which gives a finds a solution vector x to the system Ax=b, for a given matrix A and vector b.

    5. Fast Modular Computation
    6. Just as with modp1 for univariate polynomials, there is a framework for efficient computation with matrices over finite fields. This is in the LinearAlgebra[Modular] subpackage (type ?Modular to see Maple's help page). Again, we need to convert to the special representation; this time we will use Modular:-Create, Modular:-Mod, and/or Modular:-Copy to convert. Then there is a Modular counterpart of just about every standard Matrix computation, e.g. Modular:-Determinant and Modular:-LinearSolve.

  7. Where to Get Help
  8. Undoubtedly you will run into little problems, etc. when programming. Luckily, there are many resources available to you:

    • This page has a ton of information, much more than I have time to cover during the actual tutorial time. Especially useful will be (I hope) the appendix of commands below, along with Maple's online help.
    • There are lots of resources online under maplesoft.com, although most of these require a (totally free!) registration.
    • The course newsgroup uw.cs.cs487 is the ideal place to post programming questions and problems that you encounter (without sharing any solutions!), so that anyone may respond with a solution. This is likely to be much faster than a personal email to the TA or professor, and will allow everyone to benefit (it's likely that your problem is not unique).

  9. Appendix: Useful Maple Commands
  10. Just type ?command for any of these to get a synopsis of how they work.

    • Basic Arithmetic
    • +, -, *, /, ^, min, max, abs, I, eval, subs, solve, expand, simplify, sum, product, numer, denom, normal,

    • Floating Point
    • evalf, Digits, sqrt, log, log[b], floor, ceil, Pi

    • Integers
    • igcd, igcdex, ilcm, iquo, irem, isprime, nextprime, ifactor, rand, factorial, binomial

    • Modular Arithmetic
    • mod, mods, modp, &^

    • Programming
    • proc, return, if, for, while, do, local, global, nargs, error, print, lprint

    • Comparison
    • =, <, >, <=, >=, <>

    • Data
    • :=, '', "", ``, whattype, type

    • Lists, Sets, Sequences
    • [], {}, seq, nops, op, union, intersect, minus, subset

    • Polynomials
    • degree, sort, coeffs, lcoeff, tcoeff, indets, collect, content, primpart, with(PolynomialTools)

    • Polynomial Arithmetic
    • gcd, gcdex, lcm, +, -, *, ^, quo, rem, randpoly, factor, factors, irreduc, sqrfree, roots, modp1, ConvertIn, ConvertOut

    • Inert Commands
    • Gcd, Gcdex, Lcm, Eval, Quo, Rem, Factor, Factors, Roots, ...

    • Linear Algebra
    • <<...>>, with(LinearAlgebra), Matrix, Vector, Dimension, RowDimension, ColumnDimension, Determinant, Add, Multiply, MatrixInverse, RandomMatrix, LinearAlgebra[Modular], Modular:-Copy, Modular:-Mod, Modular:-Create

    • Miscellaneous
    • kernelopts(printbytes=false), time, showtime, quit, read, save, unwith, restart

Last modified on Sunday, 02 January 2011, at 22:25 hours.