|
Article information
2015 , Volume 20, ¹ 1, p.75-103
Sharaya I.A.
Boundary intervals method for visualization of polyhedral solution sets
A new method, called “boundary intervals method”, is proposed for investigation and visualization of the sets determined by systems of linear algebraic inequalities or represented as the union of solution sets to a finite number of systems of linear inequalities. Software that allows one “to visually see” various solution sets is helpful in decision making, in education, as well as for investigation of the solution sets and debugging algorithms for their estimation. At present, there exist several visualization packages for the solution sets to linear systems of relations (inequalities and equations) that can only handle systems with no more than three relations and work unsatisfactorily with unbounded and thin solution sets. All these approaches rest upon computation and further use of vertices of the polyhedral sets. The new boundary intervals method we develop is based on using so-called boundary intervals instead of vertices, which enables us to overcome the limitations of the previous approaches. The proposed method is useful, in particular, for visualization of AE-solution sets to interval linear relations systems that can consist of equations, inequalities or both. Such a possibility is based on the fact that the intersection of any AE-solution set with separate orthants of the entire space is a polyhedral set for which the determining systems of linear inequalities can be easily written out from the initial interval system of relations. The paper describes basics of the boundary intervals method for systems with two and three unknown variables. Also, we present software packages lineq and IntLinIncXX implementing the boundary intervals method and designed for visualization of the solution sets to systems of linear relations, both interval and usual noninterval.
[full text]
Keywords: boundary interval, system of linear inequalities, polytope, polyhedron, polyhedral set, visualization
Author(s):
Sharaya Irene Alexandrovna
Position: Research Scientist
Office: Institute of Computational Technologies SB RAS
Address: 630090, Russia, Novosibirsk, Ac. Lavrentiev ave, 6
E-mail: sharia@ict.nsc.ru
References:
[1] Sharaya, I.A. lineq2 — a software package for visualization of the solution sets to systems of linear inequalities. Version for Matlab: Release 25.04.2012. Available at: http://www.nsc.ru/interval/sharaya/index.html#codes
[2] Sharaya, I.A. Boundary intervals and visualization of AE-solution sets for interval system of linear equations. 15th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetics and Verified Numerics — SCAN’2012, September 23–29, 2012, Novosibirsk, Russia. Book of Abstracts. Institute of Computational Technologies, Novosibirsk, 2012. P. 166–167. Available at: http://conf.nsc.ru/files/conferences/scan2012/140000/scan2012Abstracts.pdf
[3] Sharaya, I.A. Boundary intervals and visualization of AE-solution sets for interval system of linear equations [online presentation] // 15th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetics and Verified Numerics — SCAN’2012, Novosibirsk, Russia, September 23–29, 2012. Available at: http://conf.nsc.ru/files/conferences/scan2012/142985/Sharaya-scan2012.pdf
[4] Shary, S.P. A new technique in systems analysis under interval uncertainty and ambiguity // Reliable Computing. 2002. Vol. 8, No. 5. P. 321–419. Available at: http://www.ict.nsc.ru/shary/Papers/ANewTech.pdf
[5] INTLAB — INTerval LABoratory, the Matlab toolbox for reliable computing. Available at: http://www.ti3.tu-harburg.de/rump/intlab/
[6] Popova, E., Kr¨amer, W. Visualization of parametric solution sets. Preprint BUWWRSWT 2006/10, Bergische Universit¨at Wuppertal, 2006. Available at: http://www2.math. uni-wuppertal.de/wrswt/preprints/prep_06_10-2.pdf
[7] Kramer, W. intpakX — an interval arithmetic package for Maple. Scientific Computing, Computer Arithmetic and Validated Numerics, 2006. Proceedings of SCAN 2006, 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Duisburg, Germany, September 26–29, 2006. IEEE Computer Society Press, 2007, page 27. DOI: 10.1109/SCAN.2006.29
[8] Kramer, W. Computing and visualizing solution sets of interval linear systems // Serdica J.of Comput. 2007. Vol. 1, No. 4. P. 455–468. Available at: http://serdica-comp.math.bas.bg/index.php/serdicajcomputing/article/download/33/30
[9] Popova, E., Kr¨amer, W. Visualizing parametric solution sets // BIT Numerical Mathematics. 2008. Vol. 48, iss. 1. P. 95–115. DOI: 10.1007/s10543-007-0159-3
[10] AEsolset.ps — a PostScript program for visualization of AE-solution sets to interval linear 2 × 2-systems of equations. Available at: http://www.nsc.ru/interval/Programing/AEsolset.ps
[11] Yemelichev, V.A., Kovalev, M.M., Kravtsov, M.M. Polytopes, Graphs, and Optimization. Translated by G.H. Lawden. Cambridge: Cambridge Univ. Press; 1984: 423 p.
[12] Kelley, John L. General Topology. Springer. 1975.
[13] Matlab — The language of technical computing. Available at: http://www.mathworks.com/ products/matlab
[14] Scilab — free and open source software for numerical computation. Available at: http://www.scilab.org
[15] Sharaya, I.A. IntLinInc2D — a software package for visualization of the solution sets to interval linear systems of relations with two unknowns. V ersion for Matlab: Release 01.09.2014. Available at: http://www.nsc.ru/interval/Programing, http://www.nsc.ru/interval/sharaya/index.html#codes
[16] Sharaya, I.A. IntLinInc3D — a software package for visualization of the solution sets to interval linear systems of relations with three unknowns. Version for Matlab: Release 01.09.2014. Available at: http://www.nsc.ru/interval/Programing.
Bibliography link:
Sharaya I.A. Boundary intervals method for visualization of polyhedral solution sets // Computational technologies. 2015. V. 20. ¹ 1. P. 75-103
|
