Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Analysis of the finite precision s-step biconjugate gradient method

Erin Carson and James Demmel

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2014-18
March 13, 2014

http://www.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-18.pdf

We analyze the $s$-step biconjugate gradient algorithm in finite precision arithmetic and derive a bound for the residual norm in terms of a minimum polynomial of a perturbed matrix multiplied by an amplification factor. Our bound enables comparison of $s$-step and classical biconjugate gradient in terms of amplification factors. Our results show that for $s$-step biconjugate gradient, the amplification factor depends heavily on the quality of $s$-step polynomial bases generated in each outer loop.


BibTeX citation:

@techreport{Carson:EECS-2014-18,
    Author = {Carson, Erin and Demmel, James},
    Title = {Analysis of the finite precision s-step biconjugate gradient method},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2014},
    Month = {Mar},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-18.html},
    Number = {UCB/EECS-2014-18},
    Abstract = {We analyze the $s$-step biconjugate gradient algorithm in finite precision arithmetic and derive a bound for the residual norm in terms of a minimum polynomial of a perturbed matrix multiplied by an amplification factor.  Our bound enables comparison of $s$-step and classical biconjugate gradient in terms of amplification factors. Our results show that for $s$-step biconjugate gradient, the amplification factor depends heavily on the quality of $s$-step polynomial bases generated in each outer loop.}
}

EndNote citation:

%0 Report
%A Carson, Erin
%A Demmel, James
%T Analysis of the finite precision s-step biconjugate gradient method
%I EECS Department, University of California, Berkeley
%D 2014
%8 March 13
%@ UCB/EECS-2014-18
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-18.html
%F Carson:EECS-2014-18