TITLE: An analysis of some Parallel methods for the solution of general and Toeplitz Bidiagonal Systems AUTHORS: Josep-L. Larriba-Pey(1), Juan J. Navarro(1), Oriol Roig(1) and Angel Jorba(2) (1) Departament d'Arquitectura de Computadors Universitat Politecnica de Catalunya Campus Nord, modul D-6, Gran Capita s/n 08071 Barcelona (Spain) E-mails: larri@ac.upc.es (2) Departament de Matematica Aplicada i Analisi, Universitat de Barcelona, Gran Via 585, 08007 Barcelona (Spain) E-mail: angel@maia.ub.es ABSTRACT: In this paper, a review of methods for the solution of general and Toeplitz bidiagonal systems of equations is done. Gaussian elimination, the r-Cyclic Reduction family of algorithms and the Divide and Conquer algorithm are analyzed. A unified view of the three type of methods is proposed. The work is focussed on two basic aspects of the methods: parallelism and grain. The influence of the architecture of the target computer on the parallelism and grain of the methods is evaluated. In particular, vector processors are analyzed as target architecture an one vector processor of the Convex C-3480 is taken as a case study. For the special case of Divide and Conquer, a model is made in order to tune parallelism and grain for its optimal execution. Two conclussions can be outlined from the analysis of the methods. First, the execution time of the r-Cyclic Reduction family of algorithms is lower as r grows. This means that the classic use of Cyclic Reduction on vector computers is outdated from now on. Second, the higher rank versions of the r-Cyclic Reduction family of algorithms and the optimized version of Divide and Conquer behave similarly on vector computers.