English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Recently, there has been increasing interest in using matrix-free methods tosolve linear programs due to their ability to attack extreme-scale problems.Each iteration of these methods is a matrix-vector product, so they benefitfrom a low memory footprint and are parallelized easily. Restarted primal-dualhybrid gradient (PDHG) is a matrix-free method with good practical performance.Prior analysis showed that it converges linearly on linear programs where thelinear convergence constant depends on the Hoffman constant of the KKT system.  We refine this analysis of restarted PDHG for totally unimodular linearprograms. In particular, we show that restarted PDHG finds an$\epsilon$-optimal solution in $O( H m_1^{2.5} \sqrt{\textbf{nnz}(A)} \log(Hm_2 /\epsilon) )$ matrix-vector multiplies where $m_1$ is the number ofconstraints, $m_2$ the number of variables, $\textbf{nnz}(A)$ is the number ofnonzeros in the constraint matrix, $H$ is the largest absolute coefficient inthe right hand side or objective vector, and $\epsilon$ is the distance tooptimality of the point outputted by PDHG.

Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs