Web System for Demonstrating the Syntactic Algorithms
for Solving Linear Equations in Nonnegative Integers
Dear Visitors!
It is my pleasure to present to you Web-SynDic, a student software engineering project.
Web-SynDic creates a web system to demonstrate and to distribute independently
the testing of a novel syntactic algorithm for finding integer nonnegative
solutions (Hilbert basis) of a linear Diophantine system of equations with
integer coefficients.
Web-SynDic was the first student team project based upon the required
"Software Engineering" lecture course in the computer science program.
Researcher, Dr. Dmitry Korzun, developed, proved, and implemented the algorithm
independently beyond the framework of the project and postgraduate student,
Kirill Kulakov, widely tested the implementation. The project began in June
of 2003 and the team implemented it in two phases: June 2003—March 2004 and
August 2004—November 2004.
We have now decided to publish the results of the project to foster its testing
in a worldwide community of scholars. Before doing this, we would like you to
experiment with our results. We sincerely appreciate your remarks regarding the
algorithm as well as the software. Kindly direct your comments to Dr. Dmitry Korzun
at the address: dkorzun@cs.karelia.ru
Dr. Yury A. Bogoyavlenskiy
Head of the Department of Computer Science
Petrozavodsk State University
Email: ybgv@cs.karelia.ru
The aim
The target of this project is a web system for demonstration, test and
experiment with the novel syntactic method for searching nonnegative
integer solutions of Linear Diophantine Equations (Nonnegative LDE or
NLDE). NLDEs are topical subject of research in theory and have many
important applications in integer programming, operation research and
cybernetics.
The syntactic method for solving NLDEs was firstly introduced by Miguel
Filgueiras and Ana Paula Tomas (Universidade do Porto). Their results
were later developed further by Dmitry Korzun in his PhD thesis
(Petrozavodsk State University, academic advisor Dr. Yury
Bogoyavlenskiy) with introducing new efficient algorithms for several
classes of NLDE systems.
This method is applicable for those NLDE systems that can be associated
with formal grammars. This allows to use parsing technique to search NLDE
solutions. The corresponding NLDE systems are called associated or ANLDE
the acronym for short. In many cases the method allows to construct polynomial
algorithms. This attractive property makes the algorithms to be more
efficient than "universal" solvers of arbitrary NLDE systems, particularly
for large dimensions.
Demonstration
One can see efficiency of the syntactic algorithms: time and memory
consumption of a solver running on a certain platform. Any request to
Web-SynDic for solving (searching a particular solution or Hilbert basis)
starts the syntactic solver and optionally an alternative solver. Consumed
resources are measured and showed in the report on solution. This includes
CPU time, real work time, maximum process virtual size for each solver.
Alternative solvers are supported for explicit comparison of the syntactic
algorithm with others. We are sure the syntactic algorithms are the very
reasonable way to efficiently solve large and complex ANLDE systems.
Test
The correctness of the syntactic algorithm has been proved by mathematical
methods. However the Web-SynDic system deals with implementation of. No
one can guarantee that the solver program is error-free; even many
millions of test ANLDE systems, which have been successfully solved by
this solver are not the proof yet. Nevertheless, we would like to continue
testing the implementation; each request to Web-SynDic for solving is a
test. Perhaps you will find an error or defect; We would like you to keep
taking part in this distributed testing. This helps us to make the
implementation more reliable.
Experimental analysis
In theory the complexity of the syntactic algorithm has been proved to be
polynomial. In practice this is not enough to ground the efficiency and to
recommend the algorithm for real applications. The Web-SynDic system
allows to experiment with syntactic and alternative solvers. One builds
test cases: one ANLDE system or a set of them, manual input or
automatically by a generator. Then solver runs at the test case and
Web-SynDic responds with a report, where the measured efficiency metrics
are collected for further analysis.
|
