From: jesperse@o223.nas.nasa.gov (Dennis C. Jespersen)
Newsgroups: comp.parallel
Subject: reference for burn-at-both-end tridiagonal algorithm?
Date: 17 Oct 1998 06:19:25 GMT
Organization: Computational Algorithms and Applications Branch,
Approved: bigrigg@cs.cmu.edu
Message-Id: <709ctd$7gu$1@encore.ece.cmu.edu>
Originator: bigrigg@ece.cmu.edu


Suppose we have a tridiagonal system which we know can be solved
without pivoting.  Suppose we have two processors.  A
"burn-at-both-ends" algorithm for solving the system is as follows.
Processor 1 starts at the top of the matrix and eliminates entries
below the main diagonal, processor 2 starts at the bottom of the
matrix and eliminates entries above the main diagonal.  They meet "in
the middle" and exchange a small amount of information, and each
processor solves a 2x2 linear system.  Then each processor proceeds
outward from the middle, doing a back substitution.  (There is a
description of this algorithm in terms of a particular matrix
factorization.)

I thought this was a known algorithm, but I have not been able to come
up with a reference.  Can anyone supply a reference in the literature
to this algorithm?

-- 
Dennis Jespersen                Voice: (650) 604-6742
MS T27A-1                       FAX:   (650) 604-3957
NASA Ames Research Center	email: jesperse@nas.nasa.gov
Moffett Field, CA 94035-1000    WWW:   http://science.nas.nasa.gov/~jesperse/
We have met the enemy and he is us. -- Albert, from Pogo

--
Articles to bigrigg+parallel@cs.cmu.edu (Admin: bigrigg@cs.cmu.edu)
Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel