Difference between revisions of "Bi-Conjugate Gradient Stabilized"
Craigpeli1 (talk | contribs) (→Usage) |
|||
| Line 1: | Line 1: | ||
| − | The bi-conjugate gradient stabilized method (BICGStab), | + | The multi-shifted bi-conjugate gradient stabilized method (BICGStab), |
| + | computes the solution to the problem <math> M\textbf{x} = \textbf{b}</math> | ||
| + | and, with some additional linear algebra, computes also | ||
| + | the solution to a set of shifted linear systems of the form | ||
<math>(M+\sigma_i) \textbf{x} =\textbf{b} \quad i=1,2,... ,N </math> | <math>(M+\sigma_i) \textbf{x} =\textbf{b} \quad i=1,2,... ,N </math> | ||
| − | where <math> \sigma_i</math> are the shift values. <br> | + | where <math> \sigma_i</math> are the shift values. |
| + | The main advantage of this method is that the shifted solutions do not require any | ||
| + | additional matrix-vector multiplications. If the matrix-vector multiplication cost | ||
| + | is much larger than the linear algebra cost, this routine can speed up the calculation | ||
| + | dramatically for scenarios where the shifted solutions are required. | ||
| + | <br> | ||
'''Definitions:''' <br> | '''Definitions:''' <br> | ||
| Line 13: | Line 21: | ||
# src = '''b'''. | # src = '''b'''. | ||
| − | # noShifts = | + | # noShifts = N the number of shifts. |
| − | # shifts[] = a pointer to | + | # shifts[] = a pointer to the shift value array |
| − | # sol = a pointer to an array of N pointers pointing to the solutions | + | # sol = a pointer to an array of (N+1) pointers pointing to the solutions (the first one is the no-shift solution and the rest are the shifted solutions) |
# dError = the maximum error in the solution (see definition). | # dError = the maximum error in the solution (see definition). | ||
# maxiters = the maximum number of iterations allowed. | # maxiters = the maximum number of iterations allowed. | ||
# pfncMatMult = pointer to the matrix multiplication. | # pfncMatMult = pointer to the matrix multiplication. | ||
| − | # rnd = a random vector used to | + | # rnd = a field of random vector generators -- this is used to initialize the <math> w_0 </math> vector in the BiCGstab routine. |
# the function returns the number of iterations required for convergence. | # the function returns the number of iterations required for convergence. | ||
Revision as of 04:06, 22 April 2010
The multi-shifted bi-conjugate gradient stabilized method (BICGStab), computes the solution to the problem \( M\textbf{x} = \textbf{b}\) and, with some additional linear algebra, computes also the solution to a set of shifted linear systems of the form
\((M+\sigma_i) \textbf{x} =\textbf{b} \quad i=1,2,... ,N \)
where \( \sigma_i\) are the shift values.
The main advantage of this method is that the shifted solutions do not require any
additional matrix-vector multiplications. If the matrix-vector multiplication cost
is much larger than the linear algebra cost, this routine can speed up the calculation
dramatically for scenarios where the shifted solutions are required.
Definitions:
\( \text{residue} = || ( M+\sigma_i) - \textbf{b} || \)
\( \text{error} = || ( M+\sigma_i) - \textbf{b} || / ||\textbf{b}|| \)
Usage
int qcd::bicgstabm_device(device_wilson_field &src, int noshifts, double shifts[],device_wilson_field* sol[], double dError, int maxiters, matmult<device_wilson_field>& pfncMatMult, device_random_field& rnd);
- src = b.
- noShifts = N the number of shifts.
- shifts[] = a pointer to the shift value array
- sol = a pointer to an array of (N+1) pointers pointing to the solutions (the first one is the no-shift solution and the rest are the shifted solutions)
- dError = the maximum error in the solution (see definition).
- maxiters = the maximum number of iterations allowed.
- pfncMatMult = pointer to the matrix multiplication.
- rnd = a field of random vector generators -- this is used to initialize the \( w_0 \) vector in the BiCGstab routine.
- the function returns the number of iterations required for convergence.
NOTES:
- The BICGStabM only guarantees the convergence of the linear system associated with the pfncMatMult you give it. You need to check this in your code. In fact, you should have a segment of your code check for this. If one or more shifts fails, for example, you could restart them using a single shift inverter. They should converge quickly since they probably already have almost converged to the desired accuracy.
- The example explains in more detail how to correctly use BICGStabM through an example.
You can find the example here
The code implementing the example is "control_test_bicgstabm.cu". It is located in in /gwu_qcd/inverters/ directory. You can find a .pdf of it here
