pith. sign in

arxiv: 2507.04971 · v2 · submitted 2025-07-07 · 🧮 math.NA · cs.NA

Theoretical analysis and numerical solution to a vector equation Ax-\|x\|₁x=b

Yuezhi Wang , Gwi Soo Kim , Jie Meng This is my paper

Pith reviewed 2026-05-19 06:30 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords vector equationM-matrixexistence and uniquenessstructure-preserving doubling algorithmfixed-point iterationNewton iterationnonnegative solutionnumerical solution
0
0 comments X

The pith

When A is an invertible M-matrix and b is nonnegative, the equation Ax minus the one-norm of x times x equals b has a unique nonnegative solution.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves existence and uniqueness of a nonnegative solution x to the vector equation Ax minus the L1 norm of x times x equals b, provided A is an invertible M-matrix and b is a nonnegative vector. It then develops and analyzes several numerical methods to compute that solution, including fixed-point iterations, a relaxed variant, Newton iteration, and a structure-preserving doubling algorithm. The doubling method is shown to converge at least linearly with rate one-half. A reader would care because equations of this form appear in constrained linear systems and optimization problems where nonnegativity is required, and the guarantees remove uncertainty about whether a solution exists or can be found reliably.

Core claim

For an invertible M-matrix A and nonnegative vector b, there exists a unique nonnegative vector x satisfying Ax - ||x||_1 x = b. Fixed-point iterations and Newton iteration are proposed and analyzed for computing the solution, and a structure-preserving doubling algorithm is proved applicable with convergence rate at least 1/2.

What carries the argument

The structure-preserving doubling algorithm, which iterates on structured matrices derived from the original equation to produce the solution while preserving relevant algebraic properties that ensure the linear convergence rate of at least 1/2.

If this is right

  • The nonnegative solution can be computed by the proposed fixed-point iterations and Newton method with guaranteed convergence under the stated conditions.
  • The structure-preserving doubling algorithm applies directly and converges at least linearly with rate 1/2.
  • Numerical experiments confirm that the algorithms find the solution effectively in practice.
  • The existence-uniqueness result removes ambiguity when solving such equations in applications that require nonnegative vectors.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same doubling framework might extend to related nonlinear equations that preserve similar matrix sign patterns or monotonicity properties.
  • If the M-matrix condition is relaxed slightly, the uniqueness claim could fail, suggesting a natural boundary for further theoretical work.
  • Applications in network flow or economic equilibrium models could test the algorithm on large sparse instances to measure practical speedup.

Load-bearing premise

The matrix A must be an invertible M-matrix and the vector b must be nonnegative.

What would settle it

An explicit counterexample in which A fails to be an invertible M-matrix yet the equation either has no nonnegative solution or has more than one.

Figures

Figures reproduced from arXiv: 2507.04971 by Gwi Soo Kim, Jie Meng, Yuezhi Wang.

Figure 2.1
Figure 2.1. Figure 2.1: An undirected graph where W =   4 −1 −1 −1 0 1 0 0 0 0 2 −1 0 0 −1 2   is a block upper triangular M-matrix and v = (1, 0, 0, 0)T . Suppose W admits a unique square root that is also an M-matrix and v is a nonnegative vector, we show that L = W − 1v T = (V − 1x T ) 2 , where V is the principal square root of W and x is a nonnegative vector. Without loss of generality, we write L as L = ℓ(I − W1 −… view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: Comparison of Newton method, SDA, and relaxed fixed-point iter [PITH_FULL_IMAGE:figures/full_fig_p024_5_1.png] view at source ↗
Figure 5.2
Figure 5.2. Figure 5.2: A directed graph with five nodes It can be seen that L = W − 1v T , where W =   5 −1 −1 −1 −1 0 3 −1 0 −1 0 0 2 −1 0 0 0 −1 3 −1 0 −1 0 0 2   and the vector v = [1, 0, 0, 0, 0]T . According to Section 2.4, we know that L 1 2 = W 1 2 − 1y T , where y = (W− 1 2 ) T v. We compute W 1 2 and W− 1 2 by DB iteration and obtain y = [0.4772 0.1097 0.1667 0.1097 0.1667]T . On the other hand, if we supp… view at source ↗
Figure 5.3
Figure 5.3. Figure 5.3: Improved Newton iteration (5.2) for computing the solution of equa [PITH_FULL_IMAGE:figures/full_fig_p027_5_3.png] view at source ↗
read the original abstract

Theoretical and computational properties of a vector equation $Ax-\|x\|_1x=b$ are investigated, where $A$ is an invertible $M$-matrix and $b$ is a nonnegative vector. Existence and uniqueness of a nonnegative solution is proved. Fixed-point iterations, including a relaxed fixed-point iteration and Newton iteration, are proposed and analyzed. A structure-preserving doubling algorithm is proved to be applicable in computing the required solution, the convergence is at least linear with rate 1/2. Numerical experiments are performed to demonstrate the effectiveness of the proposed algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper investigates the nonlinear vector equation Ax - ||x||_1 x = b where A is an invertible M-matrix and b is nonnegative. It proves existence and uniqueness of a nonnegative solution, proposes and analyzes fixed-point iterations (including relaxed and Newton variants), establishes applicability of a structure-preserving doubling algorithm with at least linear convergence of rate 1/2, and presents numerical experiments demonstrating effectiveness.

Significance. If the claimed proofs and convergence analysis hold, the work supplies a coherent theoretical foundation and practical algorithms for this specific nonlinear equation by exploiting standard M-matrix monotonicity and fixed-point techniques. The structure-preserving doubling algorithm with guaranteed linear convergence is a useful computational contribution, and the numerical validation strengthens the claims. This adds to the literature on nonlinear systems with M-matrices and nonnegative solutions.

minor comments (3)
  1. The abstract states that proofs and convergence analysis are given, but the introduction should explicitly outline the key steps or lemmas used in the existence-uniqueness proof to improve readability.
  2. In the description of the structure-preserving doubling algorithm, clarify what 'structure-preserving' precisely means in this context (e.g., preservation of M-matrix properties or nonnegativity) and cite the relevant theorem number.
  3. Numerical experiments section: provide more detail on the dimensions of the test problems and the specific construction of the M-matrices to allow reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive overall assessment of the manuscript. The recommendation for minor revision is noted. No specific major comments were raised in the report, so the point-by-point responses below address the referee summary and recommendation directly. We will prepare a revised version incorporating any minor editorial or presentational improvements.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained on standard M-matrix theory

full rationale

The paper proves existence and uniqueness of a nonnegative solution to Ax − ||x||₁x = b when A is an invertible M-matrix and b ≥ 0, then analyzes fixed-point iterations, Newton iteration, and a structure-preserving doubling algorithm whose convergence is shown to be at least linear with rate 1/2. These steps rest on monotonicity, fixed-point arguments, and known properties of M-matrices rather than any self-definitional reduction, fitted parameter renamed as prediction, or load-bearing self-citation chain. No equation or theorem in the provided abstract and description reduces by construction to its own inputs, so the derivation chain is independent and externally grounded.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definition and invertibility properties of M-matrices plus nonnegativity of b; no free parameters or new invented entities are introduced.

axioms (2)
  • domain assumption A is an invertible M-matrix
    Invoked as the setting that guarantees existence, uniqueness, and algorithm convergence.
  • domain assumption b is a nonnegative vector
    Required for the nonnegative solution to exist and for the iteration schemes to remain well-defined.

pith-pipeline@v0.9.0 · 5623 in / 1298 out tokens · 57486 ms · 2026-05-19T06:30:08.193029+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Alefeld and N

    G. Alefeld and N. Schneider. On square roots of M-matrices, Linear Algebra Appl., 42 (1982) 119–132

    work page 1982

  2. [2]

    Benzi, D

    M. Benzi, D. Bertaccini, F. Durastante and I. Simunec. Non-local network dynamics via fractional graph Laplacians. J. Complex Netw., 8(3) (2020) cnaa017. 27

    work page 2020

  3. [3]

    D. A. Bini, B. Iannazzo and B. Meini. Numerical Solution of Algebraic Ric- cati Equations. Volume 9 of Fundamentals of Algorithms. Society for Indus- trial and Applied Mathematics (SIAM), Philadelphia, PA, 2012

    work page 2012

  4. [4]

    D. A. Bini, B. Iannazzo and J. Meng. Geometric mean of quasi-Toeplitz matrices. BIT., (2023) 63:20

    work page 2023

  5. [5]

    D. A. Bini, B. Iannazzo, B. Meini, J. Meng and L. Robol. Computing eigen- values of semi-infinite quasi-Toeplitz matrices. Numer. Algorithms, 92 (2023) 89–118

    work page 2023

  6. [6]

    D. A. Bini, S. Massei and B. Meini. Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes. Math. Comp., 87 (2018) 2811– 2830

    work page 2018

  7. [7]

    D. A. Bini, S. Massei and B. Meini. On functions of quasi Toeplitz matrices. Sb. Math., 208 (2017) 56–74

    work page 2017

  8. [8]

    D. A. Bini, S. Massei, B. Meini and L. Robol. On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes. Numer. Linear Algebra Appl.,25 (2018) e2128

    work page 2018

  9. [9]

    D. A. Bini, S. Massei, B. Meini and L. Robol. A computational framework for two-dimensional random walks with restarts. SIAM J. Sci. Comput., 42(4) (2020) A2108–A2133

    work page 2020

  10. [10]

    D. A. Bini, S. Massei and L. Robol. Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox. Numer. Algorithms, 81 (2019) 741–769

    work page 2019

  11. [11]

    D. A. Bini, B. Meini and J. Meng. Solving quadratic matrix equations arising in random walks in the quarter plane. SIAM J. Matrix Anal. Appl., 41 (2020) 691–714

    work page 2020

  12. [12]

    D. A. Bini and B. Meini. A defect-correction algorithm for quadratic matrix equations with applications to quasi-Toeplitz matrices. Linear and Multilinear Algebra, 1–16, 2023. https://doi.org/10.1080/03081087.2023.2221988

    work page doi:10.1080/03081087.2023.2221988 2023

  13. [13]

    B¨ ottcher and S

    A. B¨ ottcher and S. M. Grudsky. Spectral Properties of Banded Toeplitz Matrices. SIAM, Philadelphia, PA (2005)

    work page 2005

  14. [14]

    B¨ ottcher and S.M

    A. B¨ ottcher and S.M. Grudsky. Toeplitz Matrices, Asymptotic Linear Al- gebra, and Functional Analysis. Birkh¨ auser Verlag, Basel (2000)

    work page 2000

  15. [15]

    B¨ ottcher and B

    A. B¨ ottcher and B. Silbermann. Introduction to Large Truncated Toeplitz Matrices. Springer-Verlag, New York (1999)

    work page 1999

  16. [16]

    Chen, H.-M

    H. Chen, H.-M. Kim and J. Meng. Algorithms for square root of semi- infinite quasi-Toeplitz M-matrices. J. Sci. Comput., (2024) 99:66

    work page 2024

  17. [17]

    Denman and A.N

    E.D. Denman and A.N. Beavers. The matrix sign function and computa- tions in systems. Appl. Math. Comput., 2 (1976) 63–94. 28

    work page 1976

  18. [18]

    N.J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008

    work page 2008

  19. [19]

    Kim and J

    H.-M. Kim and J. Meng. Structured perturbation analysis for an infi- nite size quasi-Toeplitz matrix equation with applications. BIT., 61, 859–879 (2021)

    work page 2021

  20. [20]

    I. Marek. On square roots of M-operators. Linear Algebra Appl., 223–224 (1995) 501–520

    work page 1995

  21. [21]

    J. Meng. Theoretical and computational properties of semi-infinite quasi- Toeplitz M-matrices. Linear Algebra Appl., 653 (2022) 66–85

    work page 2022

  22. [22]

    J. Meng. On a class of infinite M-matrices with an extended quasi-Toeplitz structure. Numer. Algorithms, (2025). https://doi.org/10.1007/s11075-025- 02071-3

    work page doi:10.1007/s11075-025- 2025

  23. [23]

    A. J. Motyer and P. G. Taylor. Decay rates for quasi-birth-and-death pro- cesses with countably many phases and tridiagonal block generators. Adv. Appl. Prob., 38 (2006) 522–544

    work page 2006

  24. [24]

    A. P. Riascos and J. L. Mateos. Fractional dynamics on networks: Emer- gence of anomalous diffusion and L´ evy flights. Phys. Rev. E, 90 ((2014)) 032809

    work page 2014

  25. [25]

    Shivakumar, K.C

    P.N. Shivakumar, K.C. Sivakumar and Y. Zhang. Infinite Matrices and Their Recent Applications. Springer International Publishing Switzerland, 2016

    work page 2016

  26. [26]

    Xu and L

    J. Xu and L. Liu. Analysis of a Two-Stage Tandem Queuing System with Priority and Clearing Service in the Second Stage. Mathematics, MDPI, 12(10) (2024) 1–23. 29

    work page 2024