English Version Русская версия

Кулаков Кирилл Александрович
Petrozavodsk State University,Computer Science, kulakov@cs.karelia.ru

Algorithms for Generating System of Non-negative Linear Diophantine Equations

The non-negative linear Diophantine equation (NLDE) is an equation with integer coeffi-cients and non-negative integer solutions. Our concern is a particular class of homogenous NLDE systems, associated with formal grammars — homANLDE systems. HomANLDE system solution is regarded as finding its Hilbert basis. There exist polynomial solving algorithms, based on syntac-tic analyzing methods. Using these algorithms in practice its necessary to implement them, estimate implementation reliability (solver) by means of mass testing and estimate them experimentally and compare them with alternative solvers as well. For the last stages the problem of automated genera-tion of homANLDE systems and their Hilbert basis is of current importance.
The homANLDE systems should be generated in the wide modification range of the follow-ing parameters: number of equations and unknowns in a generating system, coefficient size, number of basic solutions, etc. It does allow to carry out a homANLDE system classification and get more accurate estimates.
The paper deals with the problem of automated generation of homANLDE systems and their Hilbert basis. We have deduced theorem about the transformation of arbitrary homANLDE system to one of the two particular cases. It allows first to generate homANLDE system and their Hilbert basis for particular case, and after that execute reverse transformation. We introduce five theorem based generation algorithms. Four generation algorithms form homANLDE system subclasses and the last covers the whole homANLDE system class.
Presented generation algorithms were used for syntactic solving algorithms mass testing (more than 1.5 million systems have been tested) and are integrated into the Web-SynDic system. The latter is meant for remote demonstration, testing and experimental analysis of homANLDE sys-tems syntactic solving algorithms.