  We study the densest subgraph problem and give algorithms via multiplicative
weights update and area convexity that converge in $O\left(\frac{\log
m}{\epsilon^{2}}\right)$ and $O\left(\frac{\log m}{\epsilon}\right)$
iterations, respectively, both with nearly-linear time per iteration. Compared
with the work by Bahmani et al. (2014), our MWU algorithm uses a very different
and much simpler procedure for recovering the dense subgraph from the
fractional solution and does not employ a binary search. Compared with the work
by Boob et al. (2019), our algorithm via area convexity improves the iteration
complexity by a factor $\Delta$ -- the maximum degree in the graph, and matches
the fastest theoretical runtime currently known via flows (Chekuri et al.,
2022) in total time. Next, we study the dense subgraph decomposition problem
and give the first practical iterative algorithm with linear convergence rate
$O\left(mn\log\frac{1}{\epsilon}\right)$ via accelerated random coordinate
descent. This significantly improves over
$O\left(\frac{m\sqrt{mn\Delta}}{\epsilon}\right)$ time of the FISTA-based
algorithm by Harb et al. (2022). In the high precision regime
$\epsilon\ll\frac{1}{n}$ where we can even recover the exact solution, our
algorithm has a total runtime of $O\left(mn\log n\right)$, matching the exact
algorithm via parametric flows (Gallo et al., 1989). Empirically, we show that
this algorithm is very practical and scales to very large graphs, and its
performance is competitive with widely used methods that have significantly
weaker theoretical guarantees.
