Mathematica Developer Conference
Champaign/IL, USA 		April (11^th), 2003

by

Oliver Rübenkönig

Overview

Large numerical computations take too long -> Versatility versus performance

Timing

Performance comparison: Mathematica & MathLib
		Showcase: LU Decomposition

Accuracy of the result

Transparent user interface

More linear algebra benchmarks: Quadpack and NIntegrate

Portability

Conclusion

Note:
  			Two machines involved in computations

Versatility versus performance

({{Higher level of Abstraction
Concept: Applications based on
	Linear Algebra
	BLAS low-level abstraction

Mathematica :  high - level abstraction
	combination of numerical and 
	symbolic computation

Performance
	Automatically Tuned Linear
	Algebra Software (ATLAS)-> BLAS, }})

Need:
	To access performance of NetLib through MathLink -> MathLib

Timing

Timing measures time required by Mathematica kernel to evaluate expression.

Interfacing an external program and measuring computational times can vary greatly.

Mathematica Timing command returns unreliable results on long computations.

ATLAS interface is external -> account for time spent in Mathematica and the external program.

Solution:
	 Measure total SessionTime time and average over results.

SessionTime unfortunately allows only a resolution of seconds.

Solving dense systems of equations

Matrix A from e.g. Boundary Element Method with dimension N -> size (N^2)elements

Load vector b size N

Solution vector x size N

Direct solving  = exact (to numerical precision) solution -> LU decomposition

Many load vectors

Performance comparison:		
Mathematica & MathLib - MathLink overhead

({{Overhead of MathLink?
Problem Dimension N  / Time seconds
	Send (N^2) elements
		do nothing
	Receive back (N^2) elements
\(Comparison : 
	\ Mathematica\ LUDecomposition\)

Exporting threshold
Symmetric transfer rate
Additional memory required, }})

Strategy:
	If you move outside of Mathematica -> 
	stay there as long as possible + reduce the data transfer overhead.

Performance comparison:		
Mathematica & MathLib - DGETRF

({{
DGETRF vs. LUDecomposition
Problem Dimension N  / Time seconds

	DGETRF  =  LUDecomposition
	
	exporting threshold 
	+ external computation, }})

Observation:
	Largest time-portion of external LU decomposition is data transfer.

Performance comparison:		
Mathematica & MathLib - A large matrix

({{Complete solution
	Send matrix ((N^2))  +  load vector (N)
		compute solution
	Receive back solution vector (N)	

For N=6000 ((N^2) = 36 000 000 )-> 
70 minutes versus 6 minutes

	Mathematica kernel crash for 
		N > 6000 
	(MathLink problem?), }})

Observation:
	Can you afford to miss this opportunity ?

Performance comparison:		
Mathematica & MathLib - Multiple load vectors

({{Complete solution
	
	If you have many load vectors

	Send matrix ((N^2)) + load vectors ((N^2))
		compute solution
	Receive solution vectors ((N^2))	

	

, }})

Observation:
	LU decompositions are expensive -> recycle them if possible

Accuracy of the result

Accuracy estimate:

t is the floating-point digits (16 in our case)

α is the exponent of the condition number of the matrix ( cond(m)=(10^α) )

cond(m) is computed by

Observation:
	Solutions (for small problem sizes) always satisfied the accuracy requirement.

The transparent user interface

The following is a suggestion for a user interface:

More linear algebra benchmarks:	
Quadpack and NIntegrate

Example: Performance of (∫_(-1000)^1000) (e^(-(x^2))) dx

DQAGS uses 735 function evaluations, NIntegrate uses 440. Relative precision (10^(-6))

Pure C-Code Quadpack (double precision): 		40 times faster than NIntegrate

integralExp: Mathematica interface to DQAGS		11 times faster than NIntegrate

Improvement for high dimensional problems:
	Increased number of function evaluations but MathLink overhead remains constant

Restriction:
	We have compiled the function into the interface

More linear algebra benchmarks:	
Quadpack and NIntegrate

A more flexible solution:

Evaluate in Mathematica:			6 times slower than by NInegrate

After compiling the kernel function: 		Still slower than NIntegrate
						( 735 vs. 440 evaluations)

MathLink overhead:
	Transferring a double 735 times makes up for almost all the consumed time

Portability

Makefiles

Difficult in heterogenous university environment.

User must edit Makefile.

GNU configure

Automate makefile generation.

Familiarity with the configure-make-install cycle is increasing.

Ease to dictate the installation requirements.

Problem: on platforms where it is common to have spaces in path names.

Observation:
Average Mathematica user cannot be expected to be a programming expert
-> installation as easy as possible.
		We found that configure scripts helped.

Conclusion

High level of abstraction or good performance; not both.

->  Flexibility to decide: arbitrary precision,  high-level of abstraction, or fast libraries.

We delivered a prototype for an interface to fast libraries, ensuring its portability with GNU configure scripts.

MathLink:

->  Straightforward to use for average C programmer.

-> Overhead too restrictive for large numerical applications or often-called functions.

-> Mathematica should retain option to supply external machine tuned libraries.

How about:
Access to kernel memory to avoid data duplication in Mathematica and external program.

Thank you for your attention!

Special thanks to:				Download from:
	Prof. Dr. Jan Korvink				ftp.elmo.imtek.uni-freiburg.de:
	Dr. Evgenii Rudnyi				/pub/mathematica/MathLib.tgz