This file documents the GNU Scientific Library.

Copyright (C) 1996 The GSL Project.

Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.

Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the Foundation.

GSL
***

This file documents the the GNU Scientific Library, a collection of numerical routines for scientific computing.

Motivation
**********

There is a need for scientists and engineers to have a numerical analysis library that:

  * is free (in the sense of freedom, not in the sense of gratis; see the GNU General Public License), so that people can use that library, redistribute it, modify it ...

  * is written in C using modern coding conventions, calling conventions, scoping ...

  * is clearly and pedagogically documented; preferably with TeXinfo, so as to allow online info, WWW and TeX output.

  * uses top quality state-of-the-art algorithms.

  * is portable and configurable using autoconf and automake.

  * basically, is GNUlitically correct.

  * whatever...

There are strengths and weaknesses with existing libraries:

Netlib (http://www.netlib.org/) is probably the most advanced set of numerical algorithms available on the net, maintained by AT&T. Unfortunately most of the software is written in Fortran, with strange calling conventions in many places.  It is also not very well collected, so it is a lot of work to get started with netlib.

GAMS (http://gams.nist.gov/) is an extremely well organized set of pointers to scientific software, but like netlib, the individual routines vary in their quality and their level of documentation.

Numerical Recipies (http://www.nr.com, http://cfata2.harvard.edu/nr/) is an excellent book: it explains the algorithms in a very clear way.  Unfortunately the authors released the source code under a license which allows you to use it, but prevents you from re-distributing it.  Thus Numerical Recipes is not free in the sense of freedom.  On top of that, the implementation suffers from fortranitis and other limitations. [http://www.lysator.liu.se/c/num-recipes-in-c.html]

jt section
==========

[written by James Theiler, and not incorporated into the above motivation]

GNU Scientific Library is a library of scientific subroutines.  It aims to provide a convenient interface to ``black box'' routines that do standard (and not so standard) tasks that arise in scientific research.  More than that, it also provides the source code.  Users are welcome to alter, adjust, modify, and improve the interfaces and/or implementations of whichever routines might be needed for a particular purpose. We are starting small, with random number generators and special functions, but hope to expand to include linear algebra, Fourier analysis, etc.

Goals
-----

And we furthermore promise to try as hard as possible to document the software: this will ideally involve discussion of why you might want to use it, what precisely it does, how precisely to invoke it, how more-or-less it works, and where we learned about the algorithm, and (unless we wrote it from scratch) where we got the code. We do not plan to write this entire package from scratch, but to cannibalize existing mathematical freeware, just as we expect our own software to be cannibalized.

The long-term goal will be to provide a framework to which the real numerical experts (or their graduate students) will contribute.  Such contributors will have to contribute copylefted software and they cannot mind that evil profit-making companies (such as those which sell "environments") might use this software as part of their packages.

Design
******

Language for implementation
===========================

Issues:

One language only (C)

Advantages: simpler, compiler available and quite universal.

Disadvantages: excludes large body of old fortran code.  (Is that really a disadvantage?)

More than one language

Must be parsed by gcc (C++, objective C, fortran 77).

Routines must be trivially callable by C, without having to write wrappers.

If we do it in C

How do we protect name space, and keep global vars from being annoying? Make recommendations to implementors to help with these issues.

Interface to other languages
============================

We should propose a format for writing wrappers for other languages.

Wrapper packages are supplied as "extra" packages; not as part of the "core".

The wrapper packages can be organized either by language or by numerical subsystem.

What languages should be supported?

  * C++ (pay much attention to the design)

  * scheme/guile

  * sather

  * IDL

  * whatever

What routines are implemented
=============================

For more guidance we might look at the Forth Scientific Library [see the URL http://www.taygeta.com/fsl/sciforth.html].

Random number generators
------------------------

Includes both random number generators and routines to give various interesting distributions.

Statistics
----------

Special Functions
-----------------

What I (jt) envision for this section is a collection of routines for reliable and accurate (but not necessarily fast or efficient) estimation of values for special functions, explicitly using Taylor series, asymptotic expansions, continued fraction expansions, etc.  As well as these routines, fast approximations will also be provided, primarily based on Chebyshev polynomials and ratios of polynomials.  In this vision, the approximations will be the "standard" routines for the users, and the exact (so-called) routines will be used for verification of the approximations.  It may also be useful to provide various identity-checking routines as part of the verification suite.

Currently, the only available functions are: gsl_sf_erf() and gsl_sf_erfc()

Curve fitting
-------------

polynomial

special functions

spline

Ordinary differential equations
-------------------------------

Partial differential equations
------------------------------

Fourier Analysis
----------------

Wavelets
--------

Matrix operations: linear equations
-----------------------------------

Matrix operations: eigenvalues and spectral analysis
----------------------------------------------------

Matrix operations: any others?
------------------------------

Direct integration
------------------

Monte carlo methods
-------------------

Simulated annealing
-------------------

Genetic algorithms
------------------

We need to think about what kinds of algorithms are basic generally useful numerical algorithms, and which ones are special purpose research projects.  We should concentrate on supplying the former.

Cellular automata
-----------------

Parallel libraries
------------------

Standards and conventions
=========================

The people who kick off this project should set the coding standards and conventions.  Some standards that should be set are:

  * Targets for make.  We of course follow the GNU coding standards and use automake, so all the standard GNU targets are present.  In Test suites we discuss the possibility of a make check target which will run a verification suite for the given subsystem.

  * Function arguments and abstraction levels.

  * Sub-package function name prefixes

  * Documentation: the project leaders should give examples of how things are to be documented.  High quality documentation is absolutely mandatory, so documentation should introduce the topic, and give careful reference for the provided functions.

     I (-jt) recommend using gsl_xxx_functionName() for functions that we supply, where xxx is the 'category'.  Categories are 'ran' (random number generators), 'sf' (special functions), 'stat' (statistics), etc.

Namespace
=========

Use gsl_ as a prefix for all exported functions and variables.

Use GSL_ as a prefix for all exported macros.

All exported header files should have a filename with the prefix gsl_.

All installed libraries should have a name like libgslhistogram.a

Any installed executables (utility programs etc) should have the prefix gsl- (with a hyphen, not an underscore).

Header files
============

Installed header files should be idempotent, i.e. surround them by the preprocessor conditionals like the following,

     #ifndef GSL_HISTOGRAM_H
     ...
     #endif /* GSL_HISTOGRAM_H */

Target system
=============

The target system is ANSI C, with a full Standard C Library, and IEEE arithmetic.

Function Names
==============

Each module has a name, which prefixes any function names in that module, e.g. the module gsl_fft has function names like gsl_fft_init

Object-orientation
==================

The algorithms should be object oriented, but only to the extent that is easy in portable ANSI C.  The use of casting or other tricks to simulate inheritance is not desirable, and the user should not have to be aware of anything like that. This means many types of patterns are ruled out. However, this is not considered a problem -- they are too complicated for the library.

Note: it is possible to define an abstract base class easily in C, using function pointers. See the rng directory for an example.

Minimal structs
===============

We prefer to make structs which are minimal. For example, if a certain type of problem can be solved by several classes of algorithm (e.g. with and without derivative information) it is better to make separate types of struct to handle those cases.  i.e. run time type identification is not desirable.

Algorithm decomposition
=======================

Iterative algorithms should be decomposed into an INITIALIZE, ITERATE, TEST form, so that the user can control the progress of the iteration.

Memory allocation and ownership
===============================

Functions which allocate memory on the heap should end in _alloc (e.g. gsl_foo_alloc) and be deallocated by a corresponding _free function (gsl_foo_free).

Be sure to free any memory allocated by your function if you have to return an error in a partially initialized object.

Memory layout
=============

We use flat blocks of memory to store matrices and vectors, not C-style pointer-to-pointer arrays.  The matrices are stored in row-major order -- i.e. the column index moves continuously through memory.

Exceptions and Error handling
=============================

The basic error handling procedure is the return code (see gsl_errno.h for a list of allowed values). Use the GSL_ERROR macro to mark an error. The current definition of this macro is not ideal but it can be changed at compile time.

Be sure to free any memory allocated by your function if you return an error (in particular for errors in partially initialized objects).

Persistence
===========

If you make an object foo which uses blocks of memory (e.g. vector, matrix, histogram) you can provide functions for reading and writing those blocks,

     int gsl_foo_fread (FILE * stream, gsl_foo * v);
     int gsl_foo_fwrite (FILE * stream, const gsl_foo * v);
     int gsl_foo_fscanf (FILE * stream, gsl_foo * v);
     int gsl_foo_fprintf (FILE * stream, const gsl_foo * v, const char *format);

Only dump out the blocks of memory, not any associated parameters such as lengths. The idea is for the user to build higher level input/output facilities using the functions the library provides. Use the functions

     int gsl_block_fread (FILE * stream, gsl_block * b);
     int gsl_block_fwrite (FILE * stream, const gsl_block * b);
     int gsl_block_fscanf (FILE * stream, gsl_block * b);
     int gsl_block_fprintf (FILE * stream, const gsl_block * b, const char *format);

or

     int gsl_block_raw_fread (FILE * stream, double * b, size_t n, size_t stride);
     int gsl_block_raw_fwrite (FILE * stream, const double * b, size_t n, size_t stri
     de);
     int gsl_block_raw_fscanf (FILE * stream, double * b, size_t n, size_t stride);
     int gsl_block_raw_fprintf (FILE * stream, const double * b, size_t n, size_t str
     ide, const char *format);

to do the actual reading and writing.

Datatype widths
===============

Be aware that in ANSI C the type int is only guaranteed to provide 16-bits (or more). Therefore if you require 32 bits you must use long int, which will have 32 bits (or more).  Of course, on many platforms the type int does have 32 bits instead of 16 bits but we have to code to the ANSI standard rather than a specific platform.

size_t
======

All objects (blocks of memory, etc) should be measured in terms of a size_t type.  Therefore any iterations (e.g. for(i=0; i<N; i++)) should also use an index of type size_t.  If you need to write a descending loop you have to be careful because size_t is unsigned, so instead of

     for (i = N - 1; i >= 0 ; i--) { ... }

use something like

     for (i = 0; i < N; i++) { j = N - i ; ... }

to avoid problems with wrap-around at i=0.

Constness
=========

Use const in function prototypes wherever an object pointed to by a pointer is constant (obviously).  For variables which are meaningfully constant within a function/scope use const also. This prevents you from accidentally modifying a variable which should be constant (e.g. length of an array, etc). It can also help the compiler do optimization.  These comments also apply to arguments passed by value which should be made const when that is meaningful.

Pseudo-templates
================

There are some pseudo-template macros available in templates_on.h and templates_off.h. See a directory link block for details on how to use them.  Use sparingly, they are a bit of a nightmare, but unavoidable in places.

Test programs
=============

Provide one test program per directory which aims for 100% path coverage of the code. Obviously it would be a lot of work to really achieve this, so prioritise testing on the critical parts and use inspection for the rest.  Test all the error conditions by explicitly provoking them, because we consider it a serious defect if the function does not return an error for an invalid parameter. N.B. Don't bother to test for null pointers -- it's sufficient for the library to segfault if the user provides an invalid pointer.

The tests should be deterministic.  Use the gsl_test functions provided to perform separate tests for each feature with a separate output PASS/FAIL line, so that any failure can be uniquely identified.

Compilation
===========

Make sure everything compiles cleanly. Use the strict compilation options for extra checking.

     make CFLAGS="-ansi -pedantic -Werror -W -Wall -Wtraditional -Wconversion
       -Wshadow -Wpointer-arith -Wcast-qual -Wcast-align -Wwrite-strings
       -Wstrict-prototypes -fshort-enums -fno-common -Wmissing-prototypes
       -Wnested-externs -Dinline= -g -O4"

Also use checkergcc to check for memory problems on the stack and the heap. It's the best memory checking tool.  If checkergcc isn't available then Electric Fence will check the heap, which is better than nothing.

Make sure that the library will also compile with C++ compilers (g++). This should not be too much of a problem if you have been writing in ANSI C.

Thread-safety
=============

The library should be useable in thread-safe programs.  All the functions should be thread-safe.

We don't require everything to be completely thread safe, but any thing that isn't should be obvious, and not a function. For example, some global variables are used to control the overall behavior of the library (range-checking on/off, function to call on fatal error, etc).  Since these are accessed directly by the user they obviously aren't thread specific.

Test suites
===========

The implementor of each library should provide a reasonable test suite for that library.

The test suite should be a program that uses the library and checks the result against known results, or invokes the library several times and does a statistical analysis on the results (for example in the case of random number generators).

We should add the target make check to the Makefile.am files, and that should automatically execute the verification suite for the given library.

Legal issues
============

  * Each contributor must make sure her code is under the GNU General Public License (GPL).

  * We must understand ownership of existing code and algorithms.

       - Obviously: don't reference non-free code (such as numerical recipes).

       - I think one can reference algorithms from classic books on numerical analysis.

Non-UNIX portability
====================

There is good reason to make this library work on non-UNIX systems.  It is probably safe to ignore DOS and only worry about windows95/windowsNT portability (so filenames can be long, I think).

On the other hand, nobody should be forced to use non-UNIX systems for development.

The best solution is probably to issue guidelines for portability, like saying "don't use XYZ unless you absolutely have to".  Then the Windows people will be able to do their porting.

We should also read up on what Cygnus is doing for their win32 portability.

Compatibility with other libraries
==================================

Other libraries, such as Netlib and Numerical Recipes, are widely used. It would be good to allow drop-in replacement of these libraries, as long as that does not compromise the quality of our routines.

Compatibility should be provided by a set of wrappers, shipped as an auxiliary package.

There are probably no legal issues on this front.

Parallelism
===========

An extra sub-package with parallel libraries would be nice.  These should use standard libraries such as PVM or MPI.  (It appears that PVM ships with MPI, and vice-versa; we should figure out which is the recommended platform.)

Copying
*******

The subroutines and source code in the GNU Scientific Library package are "free"; this means that everyone is free to use them and free to redistribute them on a free basis.  The GNU Scientific Library-related programs are not in the public domain; they are copyrighted and there are restrictions on their distribution, but these restrictions are designed to permit everything that a good cooperating citizen would want to do.  What is not allowed is to try to prevent others from further sharing any version of these programs that they might get from you.

Specifically, we want to make sure that you have the right to give away copies of the programs that relate to GNU Scientific Library, that you receive source code or else can get it if you want it, that you can change these programs or use pieces of them in new free programs, and that you know you can do these things.

To make sure that everyone has such rights, we have to forbid you to deprive anyone else of these rights.  For example, if you distribute copies of the GNU Scientific Library-related code, you must give the recipients all the rights that you have.  You must make sure that they, too, receive or can get the source code.  And you must tell them their rights.

Also, for our own protection, we must make certain that everyone finds out that there is no warranty for the programs that relate to GNU Scientific Library.  If these programs are modified by someone else and passed on, we want their recipients to know that what they have is not what we distributed, so that any problems introduced by others will not reflect on our reputation.

The precise conditions of the licenses for the programs currently being distributed that relate to GNU Scientific Library are found in the General Public Licenses that accompany them.