*************************************************************************** * 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.