AN IMPLEMENTATION OF A PARALLEL ITERATIVE ALGORITHM FOR THE SOLUTION OF LARGE BANDED SYSTEM ON A CLUSTER OF WORKSTATIONS

M. Al-Towaiq, F.A.M. Masoud, A.B. Mnaouer, and K. Day

References

  1. [1] A.T. Chronopoulos & C.D. Swason, Parallel iterative s-stepmethods for unsymmetric linear systems, Parallel Computing,22, 1996, 623–641.
  2. [2] G. Haase, Parallel incomplete cholesky preconditioner basedon non-overlapping data distribution, Parallel Computing, 24,1998, 1685–1703.
  3. [3] V. Mehrmann, Divide and conquer methods for block tridi-agonal systems, Technical Report Bericht Nr. 68, Ins. FurGeometric und Prakt. Math. RWTH, Aachen, 1991.
  4. [4] B.N. Parlett, For tridiagonal T replace T with LDL, Journalof Computational & Applied Mathematics, 123, 2000, 117–130.
  5. [5] H.S. Stone, An efficient parallel algorithm for the solutionof a tridiagonal linear system of equations, Journal of theAssociation for Computing Machinery, 20, 1973, 27–38.
  6. [6] K. Sumiyoshin & T. Ebisuzaki, Performance of parallel solutionof a block-tridiagonal linear system on a Fujitus VPP 500,Parallel Computing, 24, 1998, 287–304.
  7. [7] I.S. Duff & H.A. Van der Vorst, Developments and trends inthe parallel solution of linear systems, Parallel Computing, 25,1999, 1931–1970.
  8. [8] J. Schlichting & H. Van der Vorst, Solving Bidiagonal Systemsof Linear Equations on the CDC CYBER 205, Technical ReportNM-R8725, CWI, Amsterdam, Netherlands, 1987.
  9. [9] H.S. Stone, Parallel tridiagonal equation solvers, ACM Trans-actions on Mathematical Software, 1, 1975, 289–307.
  10. [10] P. de Groen, Base p-cyclic reduction for tridiagonal systems ofequations, Applied Numerical Mathematics, 8, 1991, 117–126.
  11. [11] S.C. Chen, D.J. Kuck, & A.H. Sameh, Practical parallel bandtridiagonal system solvers, ACM Transactions on MathematicalSoftware, 4, 1978, 270–277.
  12. [12] H. Wang, A parallel method for tridiagonal equations, ACMTransactionals on Mathematical Software, 7, 1989, 170–183.
  13. [13] J.S. Kowalik & S.P. Kumar, Parallel algorithms for recurrenceand tridiagonal equations, in J.S. Kowalik (Ed.), ParallelMIMD computations; HEP supercomputer and its applications(Cambridge: MIT Press, 1995).
  14. [14] P.H. Michielse & H.A. Van der Vorst, Data transport in Wang’spartition Method, Parallel Computing, 7, 1998, 87–95.
  15. [15] I.S. Duff, A.M. Erisman, & J.K. Reid, Direct methods forsparse matrices (Oxford, England: Oxford University Press,1986).
  16. [16] J. Dongarra & L. Johnsson, Solving banded linear systems ona parallel processor, Parallel Computing, 5, 1987, 219–246.
  17. [17] S.P. Kumar, Solving tridiagonal linear systems on the butterflyparallel computer, International Journal of SupercomputerApplications, 3(1), 1989, 75–81.
  18. [18] M. Al-Towaiq, A direct method for the solution of largesystems of linear equations using incomplete LU-factorization,Mathematica Japonica, 34(5), 1989, 675–682.
  19. [19] C. Vuik, R.R.P. Van Nooyen, & P. Wesseling, Parallelism inILU-preconditioned GMRES, Parallel Computing, 24, 1998,1927–1946.Appendix APVM-Implementation of the worker process for the Tri-diagonal system./get processor id from parent/bufid=pvm_recv(pvm_parent(),node_ids_tag);info=pvm_upkint(tids,p,1);myid=pvm_mytid(); /get my id/for(i=0;i=0;i- -)f[i]=f[i]+f[i+1];if(C!=0){ele=f[0];/send the breaking element/bufid=pvm_initsend(PvmDataRaw);if(bufid<0)printf(“Can’t initsend\n”);info=pvm_pkfloat(&ele,1,1);if(info<0)printf(“can’t pack”);info=pvm_send(tids[C-1],first);}//part3if(C==0){/send f[0] from p0/t=-f[0];bufid=pvm_initsend(PvmDataRaw);384if(bufid<0)printf(“Can’t initsend\n”);info=pvm_pkfloat(&t,1,1);if(info<0)printf(“can’t pack”);info=pvm_mcast(tids,p,ftage);}else{bufid=pvm_recv(tids[0],ftage); /receive f[0]from p0/info=pvm_upkfloat(&t,1,1);}tt=-t/(n+1);t=t+(Cn/p)tt;for(i=0;i=0;i- -) {w[2]=w[0];w[0]=f[i]-xw[0]-qw[1];w[1]=w[2];}/send the breaking element to the pre-processor/if(C!=0){bufid=pvm_initsend(PvmDataRaw);if(bufid<0)printf(“Can’t initsend\n”);info=pvm_pkfloat(w,3,1);if(info<0)printf(“can’t pack”);info=pvm_send(tids[C-1],first);} //if(C!=0)}//{if(C=0;i- -)f[i]=a2(f[i]-f[i+2])-a1f[i+1];if(C!=0) {w[0]=f[0];w[1]=f[1];/send the breaking element/bufid=pvm_initsend(PvmDataRaw);if(bufid<0)printf(“Can’t initsend\n”);385info=pvm_pkfloat(w,3,1);if(info<0)printf(“can’t pack”);info=pvm_send(tids[C-1],first);}//send values of U to parentbufid=pvm_initsend(PvmDataRaw);if(bufid<0)printf(“Can’t initsend\n”);info=pvm_pkfloat(f,n/p,1);if(info<0)printf(“can’t pack”);info=pvm_send(pvm_parent(),utage);pvm_exit(); /exist pvm/}/end program/

Important Links:

Go Back