Abstract: We study the densest subgraph and give algorithms via multiplicativeweights 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 workby Bahmani et al. (2014), our MWU algorithm uses a very differentand much simpler procedure for recovering the dense subgraph fromthe fractional solution and does not employ a binary search. Comparedwith the work by Boob et al. (2019), our algorithm via area convexityimproves the iteration complexity by a factor $\Delta$---the maximumdegree in the graph, and matches the fastest theoretical runtime currentlyknown via flows (Chekuri et al., 2022) in total time. Next, westudy the dense subgraph decomposition problem and give the firstiterative algorithm with linear convergence rate $O\left(mn\log\frac{1}{\epsilon}\right)$via accelerated random coordinate descent. This significantly improvesover $O\left(\frac{m\sqrt{mn\Delta}}{\epsilon}\right)$ time of theFISTA-based algorithm by Harb et al. (2022). In the high precisionregime $\epsilon\ll\frac{1}{n}$ where we can even recover the exactsolution, our algorithm has a total runtime of $O\left(mn\log n\right)$,matching the state of the art exact algorithm via parametric flows(Gallo et al., 1989). Empirically, we show that this algorithm isvery practical and scales to very large graphs, and its performanceis competitive with widely used methods that have significantly weakertheoretical guarantees.