***************************************************************************
* THIS IS A U.S. GOVERNMENT WORK. *
* NO COPYRIGHT PROTECTION IS AVAILABLE BY 17 U.S.C. 105 *
* APPROVED FOR PUBLIC RELEASE, DISTRIBUTION IS UNLIMITED *
***************************************************************************
* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED *
* WARRANTY. IN NO EVENT, NEITHER THE AUTHORS, NOR THE PUBLISHER, NOR ANY *
* MEMBER OF THE EDITORIAL BOARD OF THE JOURNAL "NUMERICAL ALGORITHMS", *
* NOR ITS EDITOR-IN-CHIEF, BE LIABLE FOR ANY ERROR IN THE SOFTWARE, ANY *
* MISUSE OF IT OR ANY DAMAGE ARISING OUT OF ITS USE. THE ENTIRE RISK OF *
* USING THE SOFTWARE LIES WITH THE PARTY DOING SO. *
***************************************************************************
* ANY USE OF THE SOFTWARE CONSTITUTES ACCEPTANCE OF THE TERMS OF THE *
* ABOVE STATEMENT. *
***************************************************************************
AUTHORS:
Michael Jandron, Anthony Ruffa
Naval Undersea Warfare Center
E-mail: michael.jandron@navy.mil, anthony.ruffa@navy.mil
James Baglama
Department of Mathematics
University of Rhode Island
E-mail: jbaglama@uri.edu
REFERENCE:
- An asynchronous direct solver for banded linear systems
NUMERICAL ALGORITHMS, TBD (TBD), pp. TBD-TBS
SOFTWARE REVISION DATE:
v1.0, December 2016
SOFTWARE LANGUAGE:
Fortran 90 and MATLAB R2016b
=============================================================================
SOFTWARE
=============================================================================
The following are the MATLAB and FORTRAN 95 codes associated with the paper,
An asynchronous direct solver for banded linear systems. This package provides
a set of functions to solve linear systems that do not require row echelon form.
The functions are (i) Algorithm_21_TMFS.m, a Matlab function to solve tridiagonal
linear systems without exponential growth using a modified forward substitution
technique, and (ii) Algorithm_22_TMFBS.m, a Matlab function to solve tridiagonal
linear systems without exponential growth using a modified forward and backward
substitution technique, and (iii) Algorithm_31_BMFS.m, a Matlab and Fortran
function to solve banded systems using a forward substitution technique.
Note that the current implementation in Fortran requires the ISML add-on.
In Matlab, one can see a demonstration of the algorithms compared to the built-in
backslash solver by running the associated driver.m functions.
=============================================================================
PACKAGE
=============================================================================
The main directory contains the following files
README.txt : This file
** matlab files **
Algorithm_21_TMFS.m : Tridiagonal modified fwd sub algorithm
Algorithm_21_TMFS_Driver.m : Tridiagonal modified fwd sub driver
Algorithm_22_TMFBS.m : Tridiagonal modified fwd & bwrd sub algorithm
Algorithm_22_TMFBS_Driver.m : Tridiagonal modified fwd & bwrd sub driver
Algorithm_31_BMFS.m : Banded modified fwd sub algorithm
Algorithm_31_BMFS_Driver.m : Banded modified fwd sub driver
** fortran files **
Algorithm_31_BMFS.f90 : Banded modified fwd sub algorithm & driver
=============================================================================
HOW TO INSTALL
=============================================================================
When the archive file containing the package is uncompressed, the matlab and
fortran files will be shown in the base directory.
=============================================================================
HOW TO COMPILE
=============================================================================
To compile the Fortran source code, in Windows, the following switches were
used during compile to produce the results in the article. Note that
compilation requires a Fortran compiler with the ISML add-on. Without the
ISML add-on the code will not compile.
Compiler switches:
/MP
/O3
/QxHost
/Qparallel
/Qpar-threshold:10
/Qvec-threshold:10
/Qopt-prefetch=3
/heap-arrays0
/Qipo
/Qopenmp
/integer_size:64
/check:none
/threads
/Qmkl:parallel
/nologo
/libs:dll
/noD
/module:"x64\Release\\"
/object:"x64\Release\\"
/Fd"x64\Release\vc100.pdb"
/c
Linker switches
imsl_dll.lib
/OUT:"x64\Release\BMFS.exe"
/INCREMENTAL:NO
/NOLOGO
/MANIFEST
/MANIFESTFILE:"x64\Release\BMFS.exe.intermediate.manifest"
/MANIFESTUAC:"level='asInvoker' uiAccess='false'"
/SUBSYSTEM:CONSOLE
/IMPLIB: "x64\Release\BMFS.lib"
=============================================================================
NUMERICAL TESTS
=============================================================================
FORTRAN PROGRAMS :
Algorithm 3.1 Banded Modified Forward Substitution (BMFS)
- Run compiled executable to perform the benchmarking tests conducted in the
article. The code is optimized for speed so it can be adapted to fit
other linear systems if needed.
MATLAB PROGRAMS :
Algorithm 2.1 Tridiagonal Modified Forward Substitution (TMFS)
- Run Algorithm_21_TMFS_Driver.m
Requires Algorithm_21_TMFS.m to exist in the path.
This runs a test toeplitz linear system [-1,2,-1] of size n=100 with
a full RHS vector of ones and compares accuracy with the built-in
backslash solver in Matlab. Two figures will display. Figure 1 shows
the solution (x) and Figure 2 shows the error (b-Ax). In this example
the MFS solver has zero error because the use of integer arithmetic is
exact, while in the backslash solver, pivoting is used which created
floating point values and hence introduced an error on the order of
10^-13.
Algorithm 2.2 Tridiagonal Modified Forward and Backward Substitution (TMFBS)
- Run Algorithm_22_TMFBS_Driver.m
Requires Algorithm_22_TMFBS.m to exist in the path.
This runs a test toeplitz linear system [-1,2,-1] of size n=100 with
a full RHS vector of ones and compares accuracy with the built-in
backslash solver in Matlab. Two figures will display. Figure 1 shows
the solution (x) and Figure 2 shows the error (b-Ax). In this example
both show an error on the order of 10^-12.
Algorithm 3.1 Banded Modified Forward Substitution (BMFS)
- Run Algorithm_31_BMFS_Driver.m
Requires Algorithm_31_BMFS.m to exist in the path.
This runs a test unsym toeplitz linear system [-1,0,...,0,2,0,...,0,-1]
where p=15 is the lower diagonal, and q=20 is the upper diagonal,
of size n=100 with a full RHS vector of ones and compares accuracy with
the built-in backslash solver in Matlab. Three figures will display.
Figure 1 shows the spy of the matrix, Figure 2 shows the solution (x),
and Figure 3 shows the error (b-Ax). In this example both show an error
on the order of 10^-13.