Direct solution of piecewise linear systems

DOI10.1016/J.TCS.2016.02.009MaRDI QIDQ264576zbMATHOpenAlexFDO

Authors Manuel Radons

Publication date 31 March 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.09643

zbMATH Keywords

linear complementarity problemabsolute value equationdirect solverpiecewise linear equation systemsigned Gaussian elimination

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $S$ be a real $nimesn$ matrix, $z,hatcinmathbb{R}^n$, and $|z|$ the componentwise modulus of $z$. Then the piecewise linear equation system ${\displaystyle }$z-S| z| = hat c${\displaystyle }$ is called an extit{absolute value equation} (AVE). It has been proven to be equivalent to the general extit{linear complementarity problem}, which means that it is NP hard in general. We will show that for several system classes the AVE essentially retains the good natured solvability properties of regular linear systems. I.e., it can be solved directly by a slightly modified Gaussian elimination that we call the signed Gaussian elimination. For dense matrices $S$ this algorithm has the same operations count as the classical Gaussian elimination with symmetric pivoting. For tridiagonal systems in $n$ variables its computational cost is roughly that of sorting $n$ floating point numbers. The sharpness of the proposed restrictions on $S$ will be established.

Recommendations

• Convergence results for some piecewise linear solvers
• Absolute value equation solution via linear programming
• Absolute value equation solution via concave minimization
• A generalized Newton method for absolute value equations
• Linear complementarity as absolute value equation solution

Cites work

• scientific article; zbMATH DE number 5542232 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• A generalized Newton method for absolute value equations associated with second order cones
• Absolute value equation solution via concave minimization
• Absolute value equation solution via linear programming
• Absolute value equations
• Absolute value programming
• Convex sets of nonsingular and P:–Matrices
• Derived eigenvalues of symmetric matrices, with applications to distance geometry
• Direct solution of piecewise linear systems
• Introduction to Piecewise Differentiable Equations
• Iterative Solution of Piecewise Linear Systems
• Nondegenerate piecewise linear systems: finite Newton algorithm and applications in machine learning
• Solving piecewise linear systems in ABS-normal form
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• Systems of linear interval equations
• Theorems of Perron-Frobenius type for matrices without sign restrictions

Cited in

(10)

• Accelerating the Lawson-Hanson NNLS solver for large-scale Tchakaloff regression designs
• Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation
• On sign-real spectral radii and sign-real expansive matrices
• Piecewise linear regularized solution paths
• On the abs-polynomial expansion of piecewise smooth functions
• Solving piecewise linear systems in ABS-normal form
• Generalized Perron Roots and Solvability of the Absolute Value Equation
• Convergence results for some piecewise linear solvers
• Direct solution of piecewise linear systems
• Piecewise linear secant approximation via algorithmic piecewise differentiation

This page was built for publication: Direct solution of piecewise linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q264576)