Sharp Linear Bounds and Exponential Separation for Single-Flip Methods in Absolute Value Equations
Abstract
Rohn's sign-accord algorithm is a classical single-coordinate sign-flip method for Ax−|x|=b, selecting the least-index mismatched coordinate at each step. We construct rational instances on which this rule requires exactly 2n−1−1 flips from natural initialization, even when both |A−1|1 and |A−1|∞ are arbitrarily small. We propose two alternative selection rules, Gauss--Southwell and steepest single flipping, which require only one flip on the same instances. A discrete potential framework with positive polarity factors identifies solutions with global maximizers. Under positive polarity with ratio κ and r=|A−1|∞<1, both rules terminate from any initial signature after at most ⌊ sκ(1+r)/(1−r)⌋ flips, where s is the number of nonzero solution coordinates. For fixed η1<1/2 and η2<1, both rules have worst-case flip complexity O(n) on the class |A−1|1≤η1 and |A−1|∞≤η2. An n−1 lower bound from natural initialization shows that this linear order is sharp. Under stronger, explicit sign-correction conditions, each rule makes exactly as many flips as there are initially incorrect signs among the nonzero solution components. Thus, each rule makes at most n flips, and this bound is optimal. A five-dimensional example requiring six greedy flips shows that the bound of n does not extend to the entire common small-norm class. Building on Radons--Rump sign certificates, we further develop three classes of sign-flip algorithms using elimination guidance, cyclic scanning, and randomized m-flipping. Under ρ(|A−1|)<1/2, we prove at most n flips for elimination guidance, n2 inspections for cyclic scanning, and O(n2/m) expected batch updates for randomized m-flipping. Exact computations and retained paired experiments distinguish flip counts from computational cost.
Related
- Iterative Methods for Solving New Generalized Absolute Value Equations
- On exponential stability of generalized linear functional differential equations
- A weighted semigroup approach to exponential stability in linear parabolic equations
- Structure-preserving full- and low-rank exponential methods for the optimal control of Lindblad equations
- Convergence Analysis of Variable-Separation-Based Model Reduction for Linear Parametric Partial Differential Equations
BibTeX
@misc{chen2026sharp,
title = {{Sharp Linear Bounds and Exponential Separation for Single-Flip Methods in Absolute Value Equations}},
author = {Cairong Chen and Yong Xia},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.12763},
eprint = {2609.12763},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12763},
}
RIS
TY - UNPB
TI - Sharp Linear Bounds and Exponential Separation for Single-Flip Methods in Absolute Value Equations
AU - Cairong Chen
AU - Yong Xia
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.12763
UR - https://arxiv.org/abs/2609.12763
AB - Rohn's sign-accord algorithm is a classical single-coordinate sign-flip method for Ax−|x|=b, selecting the least-index mismatched coordinate at each step. We construct rational instances on which this rule requires exactly 2^n−1−1 flips from natural initialization, even when both |A^−1|_1 and |A^−1|_∞ are arbitrarily small. We propose two alternative selection rules, Gauss--Southwell and steepest single flipping, which require only one flip on the same instances. A discrete potential framework with positive polarity factors identifies solutions with global maximizers. Under positive polarity with ratio κ and r=|A^−1|_∞<1, both rules terminate from any initial signature after at most ⌊ sκ(1+r)/(1−r)⌋ flips, where s is the number of nonzero solution coordinates. For fixed η_1<1/2 and η_2<1, both rules have worst-case flip complexity O(n) on the class |A^−1|_1≤η_1 and |A^−1|_∞≤η_2. An n−1 lower bound from natural initialization shows that this linear order is sharp. Under stronger, explicit sign-correction conditions, each rule makes exactly as many flips as there are initially incorrect signs among the nonzero solution components. Thus, each rule makes at most n flips, and this bound is optimal. A five-dimensional example requiring six greedy flips shows that the bound of n does not extend to the entire common small-norm class. Building on Radons--Rump sign certificates, we further develop three classes of sign-flip algorithms using elimination guidance, cyclic scanning, and randomized m-flipping. Under ρ(|A^−1|)<1/2, we prove at most n flips for elimination guidance, n^2 inspections for cyclic scanning, and O(n^2/m) expected batch updates for randomized m-flipping. Exact computations and retained paired experiments distinguish flip counts from computational cost.
ER -