\(\mathbb N\)-solutions to linear systems over \(\mathbb Z\) (Q1827486): Difference between revisions
From MaRDI portal
m rollbackEdits.php mass rollback Tag: Rollback |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.laa.2004.01.003 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1987000381 / rank | |||
Normal rank |
Revision as of 18:43, 21 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(\mathbb N\)-solutions to linear systems over \(\mathbb Z\) |
scientific article |
Statements
\(\mathbb N\)-solutions to linear systems over \(\mathbb Z\) (English)
0 references
6 August 2004
0 references
The authors propose and compare two algorithms for computing \(\mathbb N\)-solutions to linear systems over \(\mathbb Z\). This problem is known to be NP-complete. The first algorithm uses Gröbner bases, the second uses linear programming methods. The main result of the paper is bases on the fact that the general \(\mathbb N\)-solution to a linear system over \(\mathbb Z\) can be computed by using any method for computing a particular \(\mathbb N\)-solution. This conclusion comes from the fact that the authors reduce the computation of the minimal \(\mathbb N\)-solutions or vertices, to determining a particular solution of the given system, and particular solutions of a finite number of new systems where some variables have been fixed. The reduction consists of a recursive process.
0 references
linear Diophantine equations
0 references
integer programming
0 references
Gröbner bases
0 references