# explicitly forming coarse matrices with polynomial smoothing AMG

I've been reading about the algebraic multigrid algorithm and came across polynomial smoothers in this paper. It's my understanding that usually the coarse-level matrices

$A_H = I_h^HA_hI_H^h$

are formed explicitly. However, there's still the issue of how to define the coarse space corresponding to a given smoother. The paper suggests using polynomial smoothing as an adjunct to smoothed aggregation, in which case the prolongation operator is

$I_H^h = p(A)\cdot\mathscr{I}_H^h$

where $p$ is some shifted Chebyshev polynomial and $\mathscr{I}$ is the aggregation operator.

Is explicitly forming $A_H$ with this approach prohibitively expensive? Moreover, am I even correct in assuming you need to explicitly compute the coarse level matrices?

### Do I have to form $A_H$ explicitly?

It is not strictly necessary, but if you define it implicitly, then the complexity grows from $O(n)$ to $O(n \log n)$, making the algorithm significantly less efficient. It also becomes inconvenient to define properly-scaled pointwise smoothers, which costs another factor.

### Is forming $I_H^h = p(A) \mathscr I_H^h$ and ultimately $A_H$ prohibitively expensive?

Forming $I_H^h$ is usually inexpensive because $p(A)$ is almost always chosen to be damped Jacobi (a degree 1 polynomial). Even so, construction of $A_H$ is usually the most expensvie part of multigrid setup. If $I_H^h$ were chosen to have more overlap, for example by smoothing the aggregates multiple times, grid complexity would be much higher.