Skip to main content
SpringerLink
Log in

A parallel algorithm for solving special tridiagonal systems on ring networks

Ein parelleler Algorithmus zur Lösung spezieller Tridiagonalsysteme auf Ring-Netzwerken

  • Published:
Computing Aims and scope Submit manuscript

Abstract

The solution of special linear, circulant-tridiagonal systems is considered. In this paper, a fast parallel algorithm for solving the special tridiagonal systems, which includes the skew-symmetric and tridiagonal-Toeplitz systems, is presented. Employing the diagonally dominant property, our parallel solver does need only local communications between adjacent processors on a ring network. An error analysis is also given. On the nCUBE/2E multiprocessors, some experimental results demonstrate the good performance of our stable parallel solver.

Zusammenfassung

Wir betrachten die Lösung einer Klasse von speziellen tridiagonalen Gleichungssystemen, die schiefsymmetrische und Töplitz-Systeme einschließt, und geben einen schnellen, parallelen, Algorithmus dafür an. Bei Vorliegen von Diagonal-Dominanz benötigt unser paralleler Solver nur Kommunikation zwischen benachbarten Prozessoren auf einem Ring-Netzwerk. Eine Fehleranalyse wird angegeben. Einige experimentelle Resultate, die auf einem nCUBE/2E Gerät gewonnen wurden, zeigen das gute Verhalten unseres stabilen, parallelen Solvers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Boisvert, R. F.: Algorithms for special tridiagonal systems. SIAM J. Sci. Stat. Comput.12, 423–442 (1991).

    Article  Google Scholar 

  2. Bondeli, S., Gander, W.: Cyclic reduction for special tridiagonal systems. SIAM J. Matrix Anal. Appl.15, 321–330 (1994).

    Article  Google Scholar 

  3. Chung, K. L., Yan, W. M.: A fast algorithm for cubic B-spline curve fitting. Comput. Graphics18, 327–334 (1994).

    Article  Google Scholar 

  4. Chung, K. L., Yan, W. M., Wu, J. G.: A parallel algorithm for solving special tridiagonal systems on ring networks. Research Report, Dept. Inform. Mgmt., National Taiwan Inst. of Tech. (May 1994).

  5. Dongarra, J. J., Moler, C. B., Bunch, J. R., Stewart, G. W.: LINPACK User's Guide. New York: SIAM Press 1979.

    Google Scholar 

  6. Evans D. J., Forrington, C. V. D.: Note on the solution of certain tridiagonal systems of linear equations. Comput. J.5, 327–328 (1963).

    Article  Google Scholar 

  7. Evans, D. J.: An algorithm for the solution of certain tridiagonal systems of linear equations. Comput. J.15, 356–359 (1972).

    Article  Google Scholar 

  8. Evans, D. J.: On the solution of certain Toeplitz tridiagonal linear systems. SIAM J. Numer. Anal.17, 675–680 (1980).

    Article  Google Scholar 

  9. Fischer, D., Golub, G., Hald, O., Levia, C., Winlund, O.: On Fourier-Toeplitz methods for separable elliptic problems. Math. Comput.28, 349–368 (1974).

    Google Scholar 

  10. Hockney, R. W.: A fast direct solution of Poisson's equation using Fourier analysis. J. ACM12, 95–113 (1965).

    Article  Google Scholar 

  11. Malcolm, M. A., Palmer, J.: A fast method for solving a class of tridiagonal linear systems. Comm. ACM17, 14–17 (1974).

    Article  Google Scholar 

  12. Rojo, O.: A new method for solving symmetric circulant triagonal systems of linear equations. Comput. Math. Appl.20, 12 61–67 (1990).

    Article  Google Scholar 

  13. Saad, Y., Schltz, M. H.: Topological properties of hypercubes. IEEE Trans. Comput.37, 867–872 (1988).

    Article  Google Scholar 

  14. Schmidt-Voigt, M.: Efficient parallel communication with nCUBE 2S processor. Parallel Comput.20, 509–530 (1994).

    Article  Google Scholar 

  15. Smith, G. D.: Numerical solution of partial differential equations: finite difference methods, 3rd ed. Oxford: Oxford University Press, 1985.

    Google Scholar 

  16. Widlund, O. B.: On the use of fast methods for separable finite difference equations for the solution of general elliptic problems. In Sparse matrices and their applications (Rose, D. J., Willoughby, R. A., eds.), pp. 121–131. New York: Plenum Press 1972.

    Google Scholar 

  17. Yan, W. M., Chung, K. L.: A fast algorithm for solving special tridiagonal systems. Computing52, 203–211 (1994).

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Management, National Taiwan Institute of Technology, No. 43, Section 4, Keelung Road, 10672, Taipei, Taiwan, R.O.C.

    K. -L. Chung

  2. Department of Computer Science and Information Engineering, National Taiwan University, 10764, Taipei, Taiwan, R.O.C.

    W. -M. Yan

  3. Department of Information and Computer Education, National Taiwan Normal University, 10610, Taipei, Taiwan, R.O.C.

    J. -G. Wu

Authors
  1. K. -L. Chung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. W. -M. Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. -G. Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chung, K.L., Yan, W.M. & Wu, J.G. A parallel algorithm for solving special tridiagonal systems on ring networks. Computing 56, 385–395 (1996). https://doi.org/10.1007/BF02253462

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02253462

AMS Subject Classifications

Key words

Search

Navigation