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.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Boisvert, R. F.: Algorithms for special tridiagonal systems. SIAM J. Sci. Stat. Comput.12, 423–442 (1991).
Bondeli, S., Gander, W.: Cyclic reduction for special tridiagonal systems. SIAM J. Matrix Anal. Appl.15, 321–330 (1994).
Chung, K. L., Yan, W. M.: A fast algorithm for cubic B-spline curve fitting. Comput. Graphics18, 327–334 (1994).
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).
Dongarra, J. J., Moler, C. B., Bunch, J. R., Stewart, G. W.: LINPACK User's Guide. New York: SIAM Press 1979.
Evans D. J., Forrington, C. V. D.: Note on the solution of certain tridiagonal systems of linear equations. Comput. J.5, 327–328 (1963).
Evans, D. J.: An algorithm for the solution of certain tridiagonal systems of linear equations. Comput. J.15, 356–359 (1972).
Evans, D. J.: On the solution of certain Toeplitz tridiagonal linear systems. SIAM J. Numer. Anal.17, 675–680 (1980).
Fischer, D., Golub, G., Hald, O., Levia, C., Winlund, O.: On Fourier-Toeplitz methods for separable elliptic problems. Math. Comput.28, 349–368 (1974).
Hockney, R. W.: A fast direct solution of Poisson's equation using Fourier analysis. J. ACM12, 95–113 (1965).
Malcolm, M. A., Palmer, J.: A fast method for solving a class of tridiagonal linear systems. Comm. ACM17, 14–17 (1974).
Rojo, O.: A new method for solving symmetric circulant triagonal systems of linear equations. Comput. Math. Appl.20, 12 61–67 (1990).
Saad, Y., Schltz, M. H.: Topological properties of hypercubes. IEEE Trans. Comput.37, 867–872 (1988).
Schmidt-Voigt, M.: Efficient parallel communication with nCUBE 2S processor. Parallel Comput.20, 509–530 (1994).
Smith, G. D.: Numerical solution of partial differential equations: finite difference methods, 3rd ed. Oxford: Oxford University Press, 1985.
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.
Yan, W. M., Chung, K. L.: A fast algorithm for solving special tridiagonal systems. Computing52, 203–211 (1994).
Author information
Authors and Affiliations
Rights 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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02253462