Direct solution of piecewise linear systems

DOI10.1016/J.TCS.2016.02.009zbMATH Open1336.68144arXiv1611.09643OpenAlexW2282423341MaRDI QIDQ264576FDOQ264576

Authors: Manuel Radons 

Publication date: 31 March 2016

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

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)