BBTools

Central Features

The fundamental unit in BBTools is the black-box operator (see what is a black-box for a short introduction). From this starting-point, BBTools targets the following key areas in linear algebra:

1. Creating and manipulating operators
2. SVD Analysis
3. Solving ill-posed problems
4. Iterative routines

BBTools was built to cope with larger problems than any software available to the author when the work was initiated.

Creating and manipulating operators

The fundamental idea in BBTools is to encapsulate linear operations in operators (see Operators and Hypercubes). BBTools sports a number of features for creating and working with such operators (see also Origin of Black-Box Operators):

Library of operators

Many common operators are included to provide a starting point. These may occasionally be sufficient to model real-world problems, and in time the library may grow with the help of user contributions.

Operators can be combined

Combining operators is standard in Matlab, but BBTools supports huge operators by storing an evaluation tree rather than explicit elements.

Support for custom operators

Operators can be highly specialized and require large programs to implement efficiently. If such programs are embedded in a black-box, they can be manipulated which often leads to better modularization and reuse of code.

Support for testing operators

When complex operators are implemented, it is useful to have a set of standard functions for testing the correctness of the algorithms. This is a natural part of BBTools.

SVD Analysis

The singular value decomposition (SVD) is one of the most important tools for analyzing linear systems. It forms a cornerstone of BBTools, due to its strong connection with regularized solutions of linear systems.

In its simplest form, bbsvds is meant to replace svds in the common case where some of the triplets corresponding to the largest singular values are desired. It is usually faster, partly because svds does not utilize ARPACK in the most efficient way, and partly because BBTools is designed to exploit modern hardware more efficiently.

A bit more under the hood, we find some more drastic differences:

1. bbsvds computes singular values with an amount of memory that scales as O(m+n+min(m,n)k), where k is the number of requested singular values.
   Although many packages can do this, BBTools do so without compromising the accuracy.
2. bbsvds can often compute more singular values/triplets than will fit in memory.
   This is accomplished without swapping data to and from disk; BBTools does not contain out-of-core routines. Instead, it works by trading memory for computational work. Rounding-errors prevent BBTools from computing a full SVD of a large operator, but the extension can be very useful.

Computing singular values is easier than full singular triplets. If singular vectors are required, BBTools will normally use memory that scales as O((m+n)k). The last point remains true: it is still possible to compute more triplets than memory can hold.

Solving ill-posed problems

The goal of a large linear problem is often to solve the system on the form A*x=b. Unfortunately, the system-matrix A is ill-conditioned in many practical problems and b have measurement-, rounding-, and representation-errors.

Regularization deals with these problems. BBTools is concerned with solutions that can be expressed in terms of an SVD of A and a set of filter factors. This includes many standard techniques.

Unfortunately, the SVD of A is infeasible to compute in practice, and we must resort to approximate methods. BBTools accomplishes the task in two steps:

bbpresolve

An iterative solver, except the result is not returned as a vector (bbsolve can do that). Rather, the solution is split into a number of solutions, each corresponding to a set of local filter-factors.

bbregsolve

Form a regularized solution by approximating the wanted filter-factors as a sum of the local filter-factors. The solution, x, is then a weighted sum of the solutions computed by bbpresolve.

It is typically necessary to compute a number of regularized solutions in order to balance noise and accuracy. The L-curve method (bblcurve), for instance, requires a number of of such evaluations. BBTools supports this efficiently: bbregsolve costs almost nothing when it is fed with the output from bbpresolve.

The solver in BBTools is primarily intended for ill-posed problems. When a "real" (i.e. unregularized) solution is meaningful, it may be better to use other routines.

Note that preconditioning destroys the singular values of the operator, and therefore regularization. As a consequence, the code was developed to cope with more iterations than other solvers normally expect is necessary.

Iterative routines

Black-box operators generally require iterative routines, and both the SVD routines and solvers described above are iterative. However, some problems are already handled well by existing Matlab routines. For instance, a function like eigs is excellent.

There are several cases where one may want to use the iterative solvers shipped with Matlab:

1. An exact (i.e. unregularized) solution is required.
2. A test-battery of algorithms is needed for comparison or benchmarking.
3. A known algorithm must be used to allow reproducible results.

BBTools supports most iterative routines shipped with Matlab. See the reference documentation for a full list.

In case you forgot to read the license, the stability of BBTools is not guaranteed. Later versions may do anything to any routine, including removing it from the package if the author was mad one day.

Research in iterative routines

Since the 1960s we had libraries of canned routines for most dense problems in linear algebra [5]. The libraries have been rewritten to match the technology; we went from LINPACK and EISPACK to LAPACK, and later ScaLAPACK emerged.

As computers get faster, we expect to handle larger problems, and this eventually leads to more extensive use of iterative routines [20]. The litterature is extensive, and many iterative solvers have been proposed; a good introduction can be found in [16].

Such a plethora exists because there is no single algorithm that consistenty beats the competition. No canned routine have emerged where we can leave its implementation to specialist and envoke with A\b, trusting that it "just works".

BBTools should be helpful with research of such algorithms. For instance, it allows one to evaluate the effect of degraded accuracy and count products without changing the code of the solvers.

However, the most important aspect of BBTools is perhaps that it allows the end-user a familiar entrance to the iterative routines.

References

[5] Jack J. Dongarra and David W. Walker. The Design of Linear Algebra Libraries for High Performance Computers. University of Tennessee, 1993. Reference number: UT-CS-93-188. (Technical report: )

[16] Yousef Saad and Henk A. van der Vorst. Iterative solution of linear systems in the 20th century. Journal of Computational and Applied Mathematics, 123(1-2):1-33, 2000. (Paper: )

[20] Lloyd Nicholas Trefethen and David Bau III. Numerical Linear Algebra. SIAM, Philadelphia, PA, 1997. ISBN: 0-89871-487-7. (Book)

Installation