Equation Solution  
    High Performance by Design
Navigation Menu
Home  ⇒  Numerical Analysis  ⇒  JCL  ⇓
JCL v. GPS     JCL v. Exact     JCL v. Scilab    



JCL: bandwidth and profile reduction


        JCL, a package for bandwidth and profile reduction of sparse matrix, is based on and further improving the article "Algorithms for reducing the bandwidth and profile of a sparse matrix" by J. C. Luo, published in computers & structures, vol. 44, no. 3, 1992, is a library for reducing bandwidth and profile of sparse matrix. For example, JCL re-orders the following sparse matrix
    /                          \
    |  x           x           |
    |     x  x        x     x  |
    |     x  x     x           |
    |           x        x     |
    |  x     x     x           |
    |     x           x     x  |
    |           x        x     |
    |     x           x     x  |
    \                          /
to have a minimal bandwidth as
    /                          \
    |  x  x  x                 |
    |  x  x  x                 |
    |  x  x  x  x              |
    |        x  x  x           |
    |           x  x  x        |
    |              x  x        |
    |                    x  x  |
    |                    x  x  |
    \                          /
After being reordered, the above sparse matrix can take an advantage of constant band solvers (a.k.a. band solver) and variable band solver (a.k.a. skyline solver). Band solvers require bandwidth reduction, and profile reduction is of great benefit to skyline solvers.

        JCL reduces bandwidth and profile of a sparse matrix for band solver and skyline solver. As compared with other methods, JCL can provide the best reliable result at a speed that is hard to match by other methods.

TREND OF REDUCTION

        In order to develop a method that can fit for band solver and skyline solver, the core algorithm of JCL reduces bandwidth first, and then reduces profile under the obtained bandwidth. This approach comes from the principle that profile can be reduced to a minimal value under a fixed bandwidth, but bandwidth cannot be reduced to a minimal value under a fixed profile. Bandwidth reduction should be considered first. JCL follows the trend, and is a method that can fit for band solver and skyline solver. JCL is a method for all. JCL is the best choice for bandwidth and profile reduction of sparse matrix.

SPEED THAT IS HARD TO MATCH

        JCL is a heuristic algorithm (experience-based), not exact solution algorithm. The idea to find exact solution is very simple and straightforward. For example, search the set of n! possible permutations of vertices, and it guarantees to find the exact minimal bandwidth. Exact solution algorithm is also called "brute-force-search" algorithm. However, exact solution approach is impractical beacuse it is very slow. Comparisons have shown it is not worth a trial of "brute-force-search". Especially when the size n goes up, exact solution search is useless. We need to look for heuristic algorithms.

        Heuristic approach does not have a concern of costs and execution time, but cannot guarantee the solution is the exact minimum. JCL is a heuristic algorithm. The most important point is that JCL can reduce bandwidth to the exact minimum or very close to the exact minimum at a speed that is hard to match by other methods.

        There are two other widely-applied and well-known heuristic algorithms, Cuthill-McKee algorithm ("CM") and Gibbs-Poole-Stockmeyer algorithm ("GPS"). Comparisons can show that GPS beats CM, and JCL beats GPS. JCL is capable of generating good solutions at a speed that is hard to match by other algorithms, e.g., brute-force search, tabu search, or metaheuristic. JCL is the most reliable heuristic algorithm.

IMPORTANT TOOL

        JCL reduces the cost in solving sparse system. JCL also provides a technique to number nodes for finite element analysis, finite difference method, and mesh generation. JCL is not a numerical method, but plays an important role in numerical analysis.

        For manual, click here.