PARALLEL PROCESSING OF SPARSE MATRICES HAS BEEN A DISAPPOINTING ENTERPRISE TO DATE.

PARALLEL PROCESSING OF SPARSE MATRICES HAS BEEN A DISAPPOINTING ENTERPRISE TO DATE. THE "VECTORS" THAT CAN BE PROCESSED SIMULTANEOUSLY ARE TOO SHORT TO ACHIEVE MUCH IMPROVEMENT OVER SERIAL PROCESSING. ATTEMPTS TO INCREASE THE SIZE OF THESE VECTORS SIMPLY INCREASE THE NUMBER OF OPERATIONS RATHER THAN DECREASE SOLUTION TIMES. WE SUGGEST AN ENTIRELY NEW APPROACH BASED ON THE FACTORS OF THE INVERSE. THESE FACTORS CAN BE PERFORMED IN PARALLEL, WITH ONLY TWO TO PERHAPS EIGHT SERIAL STEPS FOR LARGE SYSTEMS. IN PHASE I, WE PROPOSE TO FIND PARTITIONING SCHEMES THAT WILL ENHANCE PARALLELISM WHILE MAINTAINING SPARSITY OF THE FACTORS OF THE INVERSE, FOR VARIOUS TYPES OF SPARSE MATRIX TOPOLOGIES. THE FEASIBILITY OF THE NEW METHOD WILL BE DEMONSTRATED BY PROVIDING A SERIAL COMPUTER IMPLEMENTATION AND EVALUATING ITS PERFORMANCE ON REAL-WORLD TEST CASES. THE PROGRAM WOULD INCLUDE A BOOKKEEPING CODE TO CALCULATE POTENTIAL SPEEDUPS AVAILABLE FROM VARIOUS TYPES OF EXISTING PARALLEL ARCHITECTURES. THE DOMINANT OBJECTIVE OF THE RESEARCH IS TO TAKE FULL ADVANTAGE OF PARALLEL PROCESSOR CAPABILITIES TO ACHIEVE FASTER AND CHEAPER SPARSE MATRIX COMPUTATIONAL TECHNIQUES.