  We consider the preconditioned conjugate gradient method (PCG) with optimal
preconditioner in the frame of the boundary element method (BEM) for elliptic
first-kind integral equations. Our adaptive algorithm steers the termination of
PCG as well as the local mesh-refinement. Besides convergence with optimal
algebraic rates, we also prove almost optimal computational complexity. In
particular, we provide an additive Schwarz preconditioner which can be computed
in linear complexity and which is optimal in the sense that the condition
numbers of the preconditioned systems are uniformly bounded. As model problem
serves the 2D or 3D Laplace operator and the associated weakly-singular
integral equation with energy space $\widetilde{H}^{-1/2}(\Gamma)$. The main
results also hold for the hyper-singular integral equation with energy space
$H^{1/2}(\Gamma)$.
