Please report bugs to howell@zach.fit.edu  or gary.howell@hp.com

The codes given here have no implicit or explicit warranty.
They are free for personal or academic use.  

To extract the tar file, type
gunzip -9c bhess.tar.gz | tar xvf - 

CONTENTS OF README

1.  CONTENTS OF TAR FILE

2.  CREATING AN EXECUTABLE TESTING PROGRAM TESTBH

3.  MATLAB SCRIPTS

4.  CHECKING  THE EXECUTABLE AGAINST SAMPLE FILES 

5.  CREATING MATLAB OUTPUT THAT CAN BE CHECKED AGAINST YOUR
	EXECUTABLE  

6.  CHECKING OUTPUT FROM THE FORTRAN EXECUTABLE WITH MATLAB

7.  TESTS WITHOUT MATLAB

8.  OTHER MATERIALS


1.  CONTENTS OF TAR FILE

the tar file includes the subdirectories SRC and docs  

The SRC subdirectory contains 
   BHESS.IN      ! a sample input matrix

   README       ! current file

   SAMPOUT      ! output to compare to input matrix

   abh3.m       ! a matlab file whose results can be compared 
                ! to the Fortran results.  Also the user can 
                ! compare eigenvalues of the banded Hessenberg
                ! matrix produced by BHESS to those produced 
                ! by LAPACK routines underlying the Matlab
                ! or octave eig routines.  

   balanc.f     ! balancing routine from EISPACK -- recommended
                ! preprocessing step for finding eigenvalues. 

   bhess.f      ! warning BHESS acts on a general square matrix of 
                ! n columns but requires n+1 columns to be dimensioned
                ! as it uses a sparse column for a work vector.  

   bhtest.f     ! fortran files for testing program (use described below)

   compare.m    ! a matlab script file (use described below)

   dblas1.f     ! blas 1 routines.  tuned libraries will give faster
                ! performance. 

   makbhes      ! a unix makefile to get an executable to test BHESS 

The docs subdirectory contains 

   esub2acm.cls ! TOMS latex auxiliary file
   esub2acm.bst ! TOMS latex auxiliary file 

   howell.ps -- A preprint of a TOMS paper on bhess (and figures) 
   bandwidt.eps   ! figures 
   bdiff.eps
   blaserr.eps 
   blastime.eps
   howell01.eps
   howell02.eps
   howell03.eps
   lanczos.eps
   randerr.eps
   randerr2.eps 

The tex file howell.tex may also be included. 



2. CREATING AN EXECUTABLE TESTING PROGRAM BHTEST  

Users with UNIX can try to build a version of bhess
by moving to the SRC subdirectory and typing 

make -f makbhes

Other users will need to link the included FORTRAN files.

These files are in FORTRAN 77.  One minor extension used is
the use of an ! mark to start comments in any column.  
This extension is allowable on most FORTRAN 77 compilers and
on all FORTRAN 90 compilers.  

Performance will be greatly improved if tuned BLAS are
available instead of the dblas1.f file.  Also, typically
a -O2 or -O3 compiler option will speed execution.  

For using BHESS with other programs, only the dblas1.f file
and the bhess.f files are required.  All of the bhess and
auxiliary routines are in the file bhess.f.  All start 
with the letters BH     

The code as given does not call balanc.f (the diagonal 
rebalancing routine from EISPACK) but it is a good idea
to use such a routine as a preconditioner.   The corresponding
LAPACK routine is likely to be more efficient on modern 
machines but the time to call balanc.f is not very
significant.  


3. MATLAB SCRIPTS.   

abh3.m and compare.m are included.  

abh3.m runs from octave or matlab.
abh3.m requires tol and n and an n times n matrix a.  
abh3 performs the bhess reduction to banded
Hessenberg form b (albeit in a very inefficient way). 

Running abh3 from inside matlab or octave
produces a banded Hessenberg matrix b by bhess.

It also produces z such that 
b = float( inv(z) * a * z ) 

(A note on running the script files.
When the script stalls in matlab, hit enter,
when the script stalls in octave, hit ctrl c
once, then f for forward).  


4. CHECKING THE EXECUTABLE AGAINST SAMPLE FILES.  

Having created an executable, it is desirable to check
the correctness of the output.  

BHESS.IN is a sample output file from octave.  The file
SAMPOUT has the input matrix a, the matrix b returned by 
BHESS, z the accumulated similarity transformation,
and the results of multiplying z and inv(z) by the operations
of the BHAP1, BHAP2, and BHAP3 respectively.  

A user can test (to 8 decimal digit accuracy) SAMPOUT against
the screen output from the driver routine with input data
from BHESS.IN 


5.  CREATING MATLAB OUTPUT THAT CAN BE CHECKED AGAINST YOUR
EXECUTABLE  

First save your BHESS.IN file under a different name. 

Though very inefficient abh3 allows a user to check the proper 
operation of bhess.  There is also documentation in abh3.m which can
be accessed by typing 

help abh3

from inside octave or matlab.  

From octave for input to the Fortran exeutable 

save BHESS.IN tol n a
(then edit the resulting file to get rid of extraneous nonnumeric lines)

From matlab for input to the Fortran executable 

save BHESS.IN tol n a -ASCII 

Running the compiled file allows input from the BHESS.IN file.

The defaults for matlab or octave put the data in single precision,
so you have to declare format long (octave) to actually check accuracies.  
In matlab save with

save BHESS.IN tol n a -ASCII -DOUBLE

The included make file does not use optimized compiler options and
does not link to an optimized blas library.  For fast performance
of this code or of LAPACK you need to link to a vendor
supplied blas library.  Optimizing compiler options are
also a good idea.  


6.  CHECKING OUTPUT FROM THE FORTRAN EXECUTABLE WITH MATLAB

There is an interactive option to produce a matlab file
mat.m  

(though it is saved to only 14 digit accuracy) 

Before executing the driver, you should delete your old mat.m.

The file mat.m will contain a randomly generated matrix a
the size n, the tolerance n, and the banded Hessenberg matrix
b produced.  If you select the options for BHAP1, BHAP2, and 
BHAP3, mat.m will also contain 

onezinv = ones(1,n)*inv(z) 

z1 = z*ones(n,1)       

onesz = ones(1,n)*z

From the MATLAB prompt, the sequence of commands

mat
abh3   ( need to hit space many times)
compare

will give some error numbers

BackErr = norm(a - z*b*inv(z)) % an error internal to MATLAB 

ForErr = norm(B-b)             % forward error between MATLAB b and FORTRAN B

NormZ1Err= norm(z1-z*ones(n,1)) % vector produced by BHAP1 versus MATLAB

Norm1ZErr= norm(onez-ones(1,n)*z) % vector produced by BHAP2 versus MATLAB

Norm1InvZErr = norm(oneinvz-ones(1,n)*inv(z)) % vector procuced by BHAP3 versus MATLAB

CondZ = co  % Actual condition number of similarity transformation 

which you can compare to the estimated CondZ from BHAPC. 

(In defense of the poor formatting of the matlab-octave output, note
that most screen output commands in matlab and octave are 
not compatible). 


7.  TESTS WITHOUT MATLAB

On the next prompt after the decision whether or not to create
a matlab readable file, the input option 2 allows backward
error tests on a given matrix while varying the parameter tol. 

The driver program asks for TOL
It then applies BHESS to get a banded Hessenberg matrix B.
It then computes z*B*inv(z) 
and reports 
norm(a - z*B*inv(z)) (Frobenius norm)
norm(a-z*B*inv(z))/norm(a) (Frobenius norm of relative backward error)
estimated cond(z)
bandwidth of B 

and prompts for another TOL 

This option allows the user to experiment with the tradeoff between
TOL and bandwidth and rounding error.  


8.  OTHER MATERIALS


For further information, you can access the anonymous ftp site

cs.fit.edu

cd pub/howell

There is a CONTENTS file.  

A user interested in economical determination of eigenvalues 
by BHESS can often successfully apply the BR eigenvalue
routine (found on the above anonymous ftp site and 
documented in a SIMAX 1999 paper the BR Eigenvalue
Algorithm, by Geist, Howell, and Watkins).  













