Solving Linear Systems via Composition of their Clans

Dmitry A. ZAITSEV
DOI: 10.4236/iim.2009.12012                

Abstract

The decomposition technique for linear system solution is proposed. This technique may be combined with any known method of linear system solution. An essential acceleration of computations is obtained. Methods of linear system solution depend on the set of numbers used. For integer and especially for natural numbers all the known methods are hard enough. In this case the decomposition technique described allows the exponential acceleration of computations.

Keywords

linear system, decomposition, clans, acceleration of computation

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	F. Baader and J. Ziekmann, “Unification theory,” Handbook of logic in artificial intelligence and logic programming, Oxford: Univ. Press, pp. 1–85, 1994.
[2]	E. Contejan and F. Ajili, “Avoiding slack variables in solving linear Diophantine equations and inequations,” Theoretical Computer Science, Vol. 173, pp. 183–208, 1997.
[3]	M. A. Frumkin, “Algorithm of system of linear equations solution in integer numbers,” Research on Discrete Optimisation, Moskow, Nauka, pp. 97–127, 1976.
[4]	S. L. Kryviy, “Methods of solution and criteria of compatibility of systems of linear Diophantine equations over the set of natural numbers,” Cybernetics and Systems Analysis, Vol. 4, pp. 12–36, 1999.
[5]	J. Lloyd, “Foundation of logic programming,” Berlin, Springer-Verlag, 1987.
[6]	T. Murata, “Petri nets: Properties, analysis and applications,” Proceedings of IEEE, Vol. 77, No. 4, pp. 541–580 1989.
[7]	L. Pottier, “Minimal solutions of linear diophantine systems: bounds and algorithms,” Proceedings of the Fourth Intern. Conference on Rewriting Technique and Application, Como, Italy, pp. 162–173, 1991.
[8]	J. F. Romeuf, “A polynomial algorithm for solving systems of two linear Diophantine equations,” Theoretical Computer Science, Vol. 74, No. 3, pp. 329–340, 1990.
[9]	J. M. Toudic, “Linear algebra algorithms for the structural analysis of petri nets,” Rev. Tech. Thomson CSF, Vol. 14, No. 1, pp. 136–156, 1982.
[10]	B. L. Van Der Warden, Algebra, Berlin, Heidelberg, Springer-Verlag, 1971.
[11]	D. A. Zaitsev, “Subnets with input and output places,” Petri Net Newsletter, Vol. 64, pp. 3–6, 2003.
[12]	D. A. Zaitsev, “Formal grounding of toudic mmethod,” Proceedings of the 10th Workshop “Algorithms and Tools for Petri Nets”, Eichstaett, Germany, pp. 184–190, September 26-27, 2003.
[13]	D. A. Zaitsev and A. I. Sleptsov, “State equations and equi- valent transformations of timed petri nets,” Cybernetics and System Analysis, Vol. 33, No. 5, pp. 659–672, 1997.