[PYTHON MATRIX-SIG] Fast evaluation of numerical expressions

[Hinsen Konrad]

The following is not directly related to matrices, but I suppose most
of us are also interested in more general numerical applications of
Python.

A frequent problem with Python code for numerical applications is
speed, and the matrix module will help only in those cases where an
algorithm can be expressed in terms of matrix operations on
sufficiently large matrices. Many applications also require
the evaluation of many "simple" expressions, i.e. functions of
scalar values or small arrays.

I have thought about possibilities to speed up such calculations
without writing a special C extension module. One idea that looks
promising to me is to write a special compiler for numerical
expressions. This compiler would generate code for a simple
(and fast) stack-based expression evaluator that would be written
in C; the compiler itself could be written in Python. The
expression evaluator would not have to deal with type checks
etc., and would know the standard mathematical functions.
It could therefore be a lot faster than the general expression
evaluator in Python. In addition, the expression compiler
could be followed by an optimizer that takes care of constant
subexpressions and other things.

The compiler could most easily be constructed by defining
a new type "compiled expression" and define the usual
functions on that type. Then a user could write something
like

  x = variable(types.FloatType, 0)
  n = variable(types.IntType, 1)
  y = variable(types.FloatType, 2)
  compiled_function = sin(x**n+y)
  print compiled_function(2.5, 3, 0.3)

The function "variable" would return an object of type "compiled
expression" that pushes the n-th argument to the evaluation stack. All
the other operations would just append their code to whatever code
they get in their arguments. Variable types could be restricted to
integers, floats, complex numbers, and arrays of these types. To
compensate the lack of control structures it would probably be
necessary to introduce a conditional function; loops would be replaced
by array operations.


Does this seem like a reasonable idea? And would anyone be willing
to collaborate on an implementation? Or does anyone have a better
idea to achieve fast expression evaluation?

-------------------------------------------------------------------------------
Konrad Hinsen                     | E-Mail: hinsenk@ere.umontreal.ca
Departement de chimie             | Tel.: +1-514-343-6111 ext. 3953
Universite de Montreal            | Fax:  +1-514-343-7586
C.P. 6128, succ. Centre-Ville     | Deutsch/Esperanto/English/Nederlands/
Montreal (QC) H3C 3J7             | Francais (phase experimentale)
-------------------------------------------------------------------------------

=================
MATRIX-SIG  - SIG on Matrix Math for Python

send messages to: matrix-sig@python.org
administrivia to: matrix-sig-request@python.org
=================