×

On the computational complexity of the solution of linear systems with moduli. (English) Zbl 0853.65040

The paper deals with the computational complexity of the solution of equations of the form \(Ax= D|x|+ \delta\). Note that the problem of computing vertices of the convex hull of the united solution set for a regular system of linear interval equations reduces to the above-mentioned system. The main problem is to find a polynomial-time algorithm that finds out whether the linear system with moduli is solvable for given matrices \(A\), \(D\) and vector \(\delta\), and, in case of solvability, computes a solution to the system.
The first theorem proves that the problem of solvability of the linear system with moduli is NP-complete, if \(A\) is nonsingular, \(A\geq D\geq 0\), \(\delta\geq 0\) (the inequality “\(\geq\)” is understood componentwise), and the number of solutions of the system is finite (possibly zero).
For an arbitrary system of \(m\) equations of \(n\) variables, Theorem 2 proves that there exists a polynomial-time algorithm of order \(O((\max\{m, n\})^3)\) that finds out whether the system is solvable and computes a solution (in case of solvability) if \(A\) and \(D\) are rational matrices, \(b\) is a rational vector and \(D\geq 0\), \(\text{rank}(D)= 1\).
In a more general context, Theorem 3 states that, if \(A\), \(D\) are rational \(m\times n\)-matrices, \(b\) is a rational \(m\)-vector, and \(\text{rank}(D)+ \text{corank}(A)\leq k\), there is a polynomial-time algorithm of order \(O((\max\{m, n\})^{k+ 5})\) that finds out whether the linear system with moduli is solvable, and computes a solution in case of solvability.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65Y20 Complexity and performance of numerical algorithms
65G30 Interval and finite arithmetic
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berman, A. and Plemmons, R. J.Nonnegative matrices in the mathematical sciences. Academic Press, New York, 1979. · Zbl 0484.15016
[2] Garey, M. R. and Johnson, D. S.Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, 1979. · Zbl 0411.68039
[3] Khatchiyan, L. G.A polynomial-time algorithm for linear programming. Soviet Math. Dok.20 (1) (1979), pp. 191–194.
[4] Kupriyanova, L. V.Inner estimation of the united solution set to interval linear algebraic system. Reliable Computing1 (1) (1995), pp. 15–31. · Zbl 0844.65037
[5] Lakeyev, A. V.linear algebraic equations in Kaucher arithmetic. Reliable Computing, 1995, Supplement (Extended Abstracts of APIC’95: International Workshop on Applications of Interval Computations, El Paso, TX, Febr. 23–25, 1995), pp. 130–133.
[6] Neumaier, A.Interval methods for systems of equations. Cambridge University Press, Cambridge, 1990. · Zbl 0715.65030
[7] Rohn, J.Systems of linear interval equations. Linear Algebra Appl.126 (1989), pp. 39–78. · Zbl 0712.65029
[8] Shary, S. P.Algebraic approach to the interval linear static identification, tolerance and control problems, or One more application of Kaucher arithmetic. Reliable Computing2 (1) (1996), pp. 3–33. · Zbl 0853.65048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.