  This work analyzes the overall computational complexity of the stochastic
Galerkin finite element method (SGFEM) for approximating the solution of
parameterized elliptic partial differential equations with both affine and
non-affine random coefficients. To compute the fully discrete solution, such
approaches employ a Galerkin projection in both the deterministic and
stochastic domains, produced here by a combination of finite elements and a
global orthogonal basis, defined on an isotopic total degree index set,
respectively. To account for the sparsity of the resulting system, we present a
rigorous cost analysis that considers the total number of coupled finite
element systems that must be simultaneously solved in the SGFEM. However, to
maintain sparsity as the coefficient becomes increasingly nonlinear in the
parameterization, it is necessary to also approximate the coefficient by an
additional orthogonal expansion. In this case we prove a rigorous complexity
estimate for the number of floating point operations (FLOPs) required per
matrix-vector multiplication of the coupled system. Based on such complexity
estimates we also develop explicit cost bounds in terms of FLOPs to solve the
stochastic Galerkin (SG) systems to a prescribed tolerance, which are used to
compare with the minimal complexity estimates of a stochastic collocation
finite element method (SCFEM), shown in our previous work [16]. Finally,
computational evidence complements the theoretical estimates and supports our
conclusion that, in the case that the coefficient is affine, the coupled SG
system can be solved more efficiently than the decoupled SC systems. However,
as the coefficient becomes more nonlinear, it becomes prohibitively expensive
to obtain an approximation with the SGFEM.
