Complete solution of tropical vector inequalities using matrix sparsification

Nikolai Krivulin

Applications of Mathematics (2020)

  • Volume: 65, Issue: 6, page 755-775
  • ISSN: 0862-7940

Abstract

top
We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.

How to cite

top

Krivulin, Nikolai. "Complete solution of tropical vector inequalities using matrix sparsification." Applications of Mathematics 65.6 (2020): 755-775. <http://eudml.org/doc/296952>.

@article{Krivulin2020,
abstract = {We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.},
author = {Krivulin, Nikolai},
journal = {Applications of Mathematics},
keywords = {tropical semifield; tropical two-sided inequality; matrix sparsification; complete solution; backtracking},
language = {eng},
number = {6},
pages = {755-775},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Complete solution of tropical vector inequalities using matrix sparsification},
url = {http://eudml.org/doc/296952},
volume = {65},
year = {2020},
}

TY - JOUR
AU - Krivulin, Nikolai
TI - Complete solution of tropical vector inequalities using matrix sparsification
JO - Applications of Mathematics
PY - 2020
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 6
SP - 755
EP - 775
AB - We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.
LA - eng
KW - tropical semifield; tropical two-sided inequality; matrix sparsification; complete solution; backtracking
UR - http://eudml.org/doc/296952
ER -

References

top
  1. Akian, M., Gaubert, S., Guterman, A., 10.1142/S0218196711006674, Int. J. Algebra Comput. 22 (2012), Article ID 1250001, 43 pages. (2012) Zbl1239.14054MR2900854DOI10.1142/S0218196711006674
  2. Allamigeon, X., Gaubert, S., Katz, R. D., 10.1016/j.jcta.2010.04.003, J. Comb. Theory, Ser. A 118 (2011), 162-189. (2011) Zbl1246.14078MR2737191DOI10.1016/j.jcta.2010.04.003
  3. Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J.-P., Synchronization and Linearity: An Algebra for Discrete Event Systems, Wiley Series in Probability and Statistics. Wiley, Chichester (1992). (1992) Zbl0824.93003MR1204266
  4. Butkovič, P., 10.1007/978-1-84996-299-5, Springer Monographs in Mathematics. Springer, London (2010). (2010) Zbl1202.15032MR2681232DOI10.1007/978-1-84996-299-5
  5. Butkovič, P., Hegedüs, G., An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekon.-Mat. Obz. 20 (1984), 203-215. (1984) Zbl0545.90101MR0782401
  6. Butkovič, P., Zimmermann, K., 10.1016/j.dam.2005.09.008, Discrete Appl. Math. 154 (2006), 437-446. (2006) Zbl1090.68119MR2203194DOI10.1016/j.dam.2005.09.008
  7. Carré, B. A., 10.1093/imamat/7.3.273, J. Inst. Math. Appl. 7 (1971), 273-294. (1971) Zbl0219.90020MR0292583DOI10.1093/imamat/7.3.273
  8. Clifford, A. H., Preston, G. B., 10.1090/surv/007.1, Mathematical Surveys and Monographs 7. American Mathematical Society, Providence (1961). (1961) Zbl0111.03403MR0132791DOI10.1090/surv/007.1
  9. Cuninghame-Green, R. A., 10.1007/BF01580656, Math. Program. 10 (1976), 111-123. (1976) Zbl0336.90062MR0403664DOI10.1007/BF01580656
  10. Cuninghame-Green, R. A., 10.1007/978-3-642-48708-8, Lecture Notes in Economics and Mathematical Systems 166. Springer, Berlin (1979). (1979) Zbl0399.90052MR0580321DOI10.1007/978-3-642-48708-8
  11. Cuninghame-Green, R. A., 10.1016/S1076-5670(08)70083-1, Advances in Imaging and Electron Physics. Volume 90 Academic Press, San Diego (1994), 1-121. (1994) MR0580321DOI10.1016/S1076-5670(08)70083-1
  12. Cuninghame-Green, R. A., Butkovič, P., 10.1016/S0304-3975(02)00228-1, Theor. Comput. Sci. 293 (2003), 3-12. (2003) Zbl1021.65022MR1957609DOI10.1016/S0304-3975(02)00228-1
  13. Cuninghame-Green, R. A., Butkovič, P., 10.1016/j.laa.2004.03.022, Linear Algebra Appl. 389 (2004), 107-120. (2004) Zbl1059.15001MR2080398DOI10.1016/j.laa.2004.03.022
  14. Elsner, L., Driessche, P. van den, 10.1016/j.laa.2009.10.005, Linear Algebra Appl. 432 (2010), 927-935. (2010) Zbl1191.15019MR2577637DOI10.1016/j.laa.2009.10.005
  15. Gaubert, S., Katz, R. D., 10.1016/j.laa.2009.03.012, Linear Algebra Appl. 431 (2009), 608-625. (2009) Zbl1172.52002MR2535537DOI10.1016/j.laa.2009.03.012
  16. Gaubert, S., Katz, R. D., Sergeev, S., 10.1016/j.jsc.2011.12.049, J. Symb. Comput. 47 (2012), 1447-1478. (2012) Zbl1270.90081MR2929038DOI10.1016/j.jsc.2011.12.049
  17. Golan, J. S., 10.1007/978-94-017-0383-3, Mathematics and Its Applications 556. Kluwer Academic, Dordrecht (2003). (2003) Zbl1042.16038MR1997126DOI10.1007/978-94-017-0383-3
  18. Gondran, M., Minoux, M., 10.1007/978-0-387-75450-5, Operations Research/Computer Science Interfaces Series 41. Springer, New York (2008). (2008) Zbl1201.16038MR2389137DOI10.1007/978-0-387-75450-5
  19. Heidergott, B., Olsder, G. J., Woude, J. van der, 10.1515/9781400865239, Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2006). (2006) Zbl1130.93003MR2188299DOI10.1515/9781400865239
  20. Jones, D., 10.1016/j.dam.2018.06.011, Discrete Appl. Math. 254 (2019), 146-160. (2019) Zbl1407.15017MR3913099DOI10.1016/j.dam.2018.06.011
  21. Kolokoltsov, V. N., Maslov, V. P., 10.1007/978-94-015-8901-7, Mathematics and Its Applications 401. Kluwer Academic, Dordrecht (1997). (1997) Zbl0941.93001MR1447629DOI10.1007/978-94-015-8901-7
  22. Krivulin, N. K., Solution of generalized linear vector equations in idempotent algebra, Vestn. St. Petersbg. Univ., Math. 39 (2006), 16-26. (2006) MR2302633
  23. Krivulin, N., 10.1080/02331934.2013.840624, Optimization 64 (2015), 1107-1129. (2015) Zbl1311.65086MR3316792DOI10.1080/02331934.2013.840624
  24. Krivulin, N., 10.1016/j.laa.2014.06.044, Linear Algebra Appl. 468 (2015), 211-232. (2015) Zbl1307.65089MR3293251DOI10.1016/j.laa.2014.06.044
  25. Krivulin, N., 10.1016/j.jlamp.2017.03.004, J. Log. Algebr. Methods Program. 89 (2017), 150-170. (2017) Zbl1386.90174MR3634737DOI10.1016/j.jlamp.2017.03.004
  26. Krivulin, N., 10.1016/j.jlamp.2018.05.002, J. Log. Algebr. Methods Program. 99 (2018), 26-40. (2018) Zbl1412.90143MR3811166DOI10.1016/j.jlamp.2018.05.002
  27. Lorenzo, E., Puente, M. J. de la, 10.1016/j.laa.2011.02.014, Linear Algebra Appl. 435 (2011), 884-901. (2011) Zbl1217.65076MR2807241DOI10.1016/j.laa.2011.02.014
  28. Sergeev, S., 10.1090/conm/495, Tropical and Idempotent Mathematics Contemporary Mathematics 495. American Mathematical Society, Providence (2009), 317-342. (2009) Zbl1179.15033MR2581526DOI10.1090/conm/495
  29. Sergeev, S., Wagneur, E., 10.1016/j.laa.2011.02.033, Linear Algebra Appl. 435 (2011), 1758-1768. (2011) Zbl1227.15018MR2810669DOI10.1016/j.laa.2011.02.033
  30. Wagneur, E., Truffet, L., Faye, F., Thiam, M., 10.1090/conm/495, Tropical and Idempotent Mathematics Contemporary Mathematics 495. American Mathematical Society, Providence (2009), 351-366. (2009) Zbl1357.15017MR2581528DOI10.1090/conm/495
  31. Yoeli, M., 10.2307/2311149, Am. Math. Mon. 68 (1961), 552-557. (1961) Zbl0115.02103MR0126472DOI10.2307/2311149
  32. Zimmermann, K., A general separation theorem in extremal algebras, Ekon.-Mat. Obz. 13 (1977), 179-201. (1977) Zbl0365.90127MR0453607

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.