Resolution of a system of the MAX-product fuzzy relation equations using \( L \circ U\)-factorization.

*(English)*Zbl 1284.65045Summary: In this paper, the \(LU\)-factorization is extended to the fuzzy square matrix with respect to the max-product composition operator called \( L \circ U\)-factorization. Equivalently, we will find two fuzzy (lower and upper) triangular matrices \( L\) and \( U\) for a fuzzy square matrix \( A\) such that \(A= L \circ U\), where “\(\circ \)” is the max-product composition. An algorithm is presented to find the matrices \( L\) and \( U\). Furthermore, some necessary and sufficient conditions are proposed for the existence and uniqueness of the \( L \circ U\)-factorization for a given fuzzy square matrix \( A\). An algorithm is also proposed to find the solution set of a square system of Fuzzy Relation Equations (FRE) using the \( L \circ U\)-factorization. The algorithm finds the solution set without finding its minimal solutions and maximum solution. It is shown that the two algorithms have a polynomial-time complexity as \(O(n^3)\). Since the determination of the minimal solutions is an NP-hard problem, the algorithm can be very important from the practical point of view.

##### MSC:

65F05 | Direct numerical methods for linear systems and matrix inversion |

03E72 | Theory of fuzzy sets, etc. |

15B15 | Fuzzy matrices |

Full Text:
DOI

##### References:

[1] | Abbasbandy, S.; Babolian, E.; Allame, M., Numerical solution of fuzzy MAX-MIN systems, Applied Mathematics and Computation, 174, 1321-1328, (2006) · Zbl 1094.65035 |

[2] | Abbasi Molai, A.; Khorram, E., An algorithm for solving fuzzy relation equations with MAX-T composition operator, Information Sciences, 178, 1293-1308, (2008) · Zbl 1136.03330 |

[3] | Arnould, T.; Tano, S., A rule-based method to calculate the widest solution sets of a MAX-MIN fuzzy relational equation, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2, 247-256, (1994) · Zbl 1232.03037 |

[4] | Arnould, T.; Tano, S., A rule-based method to calculate exactly the widest solution sets of a MAX-MIN fuzzy relational inequality, Fuzzy Sets and Systems, 64, 39-58, (1994) · Zbl 1232.03037 |

[5] | Allame, M.; Vatankhahan, B., Iteration algorithm for solving ax=b in MAX-MIN algebra, Applied Mathematics and Computation, 175, 269-276, (2006) · Zbl 1088.65027 |

[6] | Bour, L.; Lamotte, M., Solutions minimales d’équations de relations floues avec la composition MAX t-norme, BUSEFAL, 31, 24-31, (1987) · Zbl 0633.04002 |

[7] | Bourke, M. M.; Fisher, D. G., Solution algorithms for fuzzy relational equations with MAX-product composition, Fuzzy Sets and Systems, 94, 61-69, (1998) · Zbl 0923.04003 |

[8] | Cechlárová, K., Unique solvability of MAX-MIN fuzzy equations and strong regularity of matrices over fuzzy algebra, Fuzzy Sets and Systems, 75, 165-177, (1995) · Zbl 0852.15011 |

[9] | Chen, L.; Wang, P. P., Fuzzy relation equations (I): the general and specialized solving algorithms, Soft Computing, 6, 428-435, (2002) · Zbl 1024.03520 |

[10] | Chen, L.; Wang, P. P., Fuzzy relation equations (II): the branch-poit-solutions and the categorized minimal solutions, Soft Computing, 11, 33-40, (2007) · Zbl 1108.03310 |

[11] | Cuninghame-Green, R. A., Minimax algebra, Lecture Notes in Economics and Mathematical Systems, 166, (1979), Springer Berlin |

[12] | Czogala, E.; Drewniak, J.; Pedrycz, W., Fuzzy relation equations on a finite set, Fuzzy Sets and Systems, 7, 89-101, (1982) · Zbl 0483.04001 |

[13] | De Baets, B., Analytical solution methods for fuzzy relational equations, (Dubois, D.; Prade, H., Fundamentals of Fuzzy Sets, The Handbooks of Fuzzy Sets Series, (2000), Kluwer Academic Publishers Dordrecht), pp. 291-340 · Zbl 0970.03044 |

[14] | Di Nola, A., An algorithm of calculation of lower solutions of fuzzy relation equation, Stochastica, 3, 33-40, (1984) · Zbl 0593.04005 |

[15] | Di Nola, A.; Pedrycz, W.; Sessa, S., On solution of fuzzy relational equations and their characterization, BUSEFAL, 12, 60-71, (1982) |

[16] | Di Nola, A.; Russo, C., Lukasiewicz transform and its application to compression and reconstruction of digital images, Information Sciences, 177, 1481-1498, (2007) · Zbl 1114.06009 |

[17] | Di Nola, A.; Sessa, S.; Pedrycz, W.; Sanchez, E., Fuzzy relation equations and their applications to knowledge engineering, (1989), Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 0694.94025 |

[18] | Fernandez, M. J.; Gil, P., Some specific types of fuzzy relation equations, Information Sciences, 164, 189-195, (2004) · Zbl 1058.03058 |

[19] | Ghodousian, A.; Khorram, E., Fuzzy linear optimization in the presence of the fuzzy relation inequality constraints with MAX-MIN composition, Information Sciences, 178, 501-519, (2008) · Zbl 1149.90189 |

[20] | Gottwald, S., Mathematical fuzzy logic as a tool for the treatment of vague information, Information Sciences, 172, 41-71, (2005) · Zbl 1079.03014 |

[21] | Han, S. R.; Sekiguchi, T., Solution of a fuzzy relation equation using a sign matrix, Japanese Journal of Fuzzy Theory and Systems, 4, 160-171, (1992) |

[22] | Higashi, M.; Klir, G. J., Resolution of finite fuzzy relation equations, Fuzzy Sets and Systems, 13, 65-82, (1984) · Zbl 0553.04006 |

[23] | Klir, G.; Yuan, B., Fuzzy sets and fuzzy logic: theory and applications, Upper Saddle River, (1995), Prentice Hall NJ |

[24] | Li, P.; Fang, S.-C., A survey on fuzzy relational equations part I: classification and solvability, Fuzzy Optimization and Decision Making, 8, 179-229, (2009) · Zbl 1180.03051 |

[25] | Li, J.-X., On an algorithm for solving fuzzy linear systems, Fuzzy Sets and Systems, 61, 369-371, (1994) · Zbl 0826.04004 |

[26] | Li, H. X.; Miao, Z. H.; Han, S. C.; Wang, J. Y., A new kind of fuzzy relation equations based on inner transformation, Computers and Mathematics with Applications, 50, 623-636, (2005) · Zbl 1085.03043 |

[27] | Li, P.; Fang, S.-C., On the resolution and optimization of a system of fuzzy relational equations with sup-T composition, Fuzzy Optimization and Decision Making, 7, 169-214, (2008) · Zbl 1169.90493 |

[28] | Lichung, C.; Boxing, P., The fuzzy relation equation with union or intersection preserving operator, Fuzzy Sets and Systems, 25, 191-204, (1988) · Zbl 0651.04005 |

[29] | Lin, J.-L., On the relation between fuzzy MAX-Archimedean t-norm relational equations and the covering problem, Fuzzy Sets and Systems, 160, 2328-2344, (2009) · Zbl 1181.03055 |

[30] | Loetamonphong, J.; Fang, S.-C., An efficient solution procedure for fuzzy relation equations with MAX-product composition, IEEE Transactions on Fuzzy Systems, 7, 441-445, (1999) |

[31] | Loia, V.; Sessa, S., Fuzzy relation equations for coding/decoding processes of images and videos, Information Sciences, 171, 145-172, (2005) · Zbl 1078.68815 |

[32] | Luoh, L.; Wang, W. J.; Liaw, Y. K., New algorithms for solving fuzzy relation equations, Mathematics and Computers in Simulation, 59, 329-333, (2002) · Zbl 0999.03513 |

[33] | Luoh, L.; Wang, W. J.; Liaw, Y. K., Matrix-pattern-based computer algorithm for solving fuzzy relation equations, IEEE Transactions on Fuzzy Systems, 11, 100-108, (2003) |

[34] | Luoh, L.; Liaw, Y.-K., Novel approximate solving algorithm for fuzzy relational equations, Mathematical and Computer Modelling, 52, 303-308, (2010) · Zbl 1201.90209 |

[35] | Markovskii, A., On the relation between equations with MAX-product composition and the covering problem, Fuzzy Sets and Systems, 153, 261-273, (2005) · Zbl 1073.03538 |

[36] | Markovskii, A., Solution of fuzzy equations with MAX-product composition in inverse control and decision making problems, Automation and Remote Control, 65, 1486-1495, (2004) · Zbl 1114.90488 |

[37] | Miyakoshi, M.; Shimbo, M., Solutions of composite fuzzy relational equations with triangular norms, Fuzzy Sets and Systems, 16, 53-63, (1985) · Zbl 0582.94031 |

[38] | Miyakoshi, M.; Shimbo, M., Lower solutions of systems of fuzzy equations, Fuzzy Sets and Systems, 19, 37-46, (1986) · Zbl 0628.04004 |

[39] | Nobuhara, H.; Bede, B.; Hirota, K., On various eigen fuzzy sets and their application to image reconstruction, Information Sciences, 176, 2988-3010, (2006) · Zbl 1102.68697 |

[40] | Nobuhara, H.; Pedrycz, W.; Sessa, S.; Hirota, K., A motion compression/reconstruction method based on MAX t-norm composite fuzzy relational equations, Information Sciences, 176, 2526-2552, (2006) · Zbl 1102.68698 |

[41] | Pappis, C. P.; Sugeno, M., Fuzzy relational equations and the inverse problem, Fuzzy Sets and Systems, 15, 79-90, (1985) · Zbl 0561.04003 |

[42] | Pedrycz, W., Fuzzy relational equations with triangular norms and their resolutions, BUSEFAL, 11, 24-32, (1982) · Zbl 0498.04004 |

[43] | Pedrycz, W., On generalized fuzzy relational equations and their applications, Journal of Mathematical Analysis and Applications, 107, 520-536, (1985) · Zbl 0581.04003 |

[44] | Peeva, K., Systems of linear equations over a bounded chain, Acta Cybernetica, 7, 195-202, (1985) · Zbl 0584.68074 |

[45] | Peeva, K., Fuzzy linear systems, Fuzzy Sets and Systems, 49, 339-355, (1992) · Zbl 0805.04005 |

[46] | Peeva, K.; Kyosev, Y., Fuzzy relational calculus: theory, applications and software, (2004), World Scientific New Jersey · Zbl 1083.03048 |

[47] | Peeva, K., Universal algorithm for solving fuzzy relational equations, Italian Journal of Pure and Applied Mathematics, 9, 9-20, (2006) · Zbl 1137.03030 |

[48] | Peeva, K.; Kyosev, Y., Algorithm for solving MAX-product fuzzy relational equations, Soft Computing, 11, 593-605, (2007) · Zbl 1113.65042 |

[49] | Perfilieva, I.; Novak, V., System of fuzzy relation equations as a continuous model of IF-THEN rules, Information Sciences, 177, 3218-3227, (2007) · Zbl 1124.03029 |

[50] | Prevot, M., Algorithm for the solution of fuzzy relations, Fuzzy Sets and Systems, 5, 319-322, (1981) · Zbl 0451.04004 |

[51] | Qu, X.-B.; Wang, X.-P., Minimization of linear objective functions under the constraints expressed by a system of fuzzy relation equations, Information Sciences, 178, 3482-3490, (2008) · Zbl 1190.90300 |

[52] | Sanchez, E., Equations de Relations Floves, Thèse Biologie Humaine, (1972), Marseille France |

[53] | E. Sanchez, Equations de relation floues, Thèse de Doctorat, Faculté de Médecine de Marseille, 1974. |

[54] | Sanchez, E., Resolution of composite fuzzy relation equation, Information and Control, 30, 38-48, (1976) · Zbl 0326.02048 |

[55] | Sanchez, E., Solutions in composite fuzzy relation equations: application to medical diagnosis in Brouwerian logic, (Gupta, M. M.; Saridis, G. N.; Gaines, B. R., Fuzzy automata and decision processes, (1977), Amsterdam North-Holland), pp. 221-234 |

[56] | Shi, E. W., The hypothesis on the number of lower solutions of a fuzzy relation equation, BUSEFAL, 31, 32-41, (1987) · Zbl 0645.04005 |

[57] | Shieh, B.-S., Solutions of fuzzy relation equations based on continuous t-norms, Information Sciences, 177, 4208-4215, (2007) · Zbl 1122.03054 |

[58] | Shieh, B.-S., Deriving minimal solutions for fuzzy relation equations with MAX-product composition, Information Sciences, 178, 3766-3774, (2008) · Zbl 1151.03345 |

[59] | Shieh, B.-S., Infinite fuzzy relation equations with continuous t-norms, Information Sciences, 178, 1961-1967, (2008) · Zbl 1135.03346 |

[60] | Shieh, B.-S., Minimizing a linear objective function under a fuzzy MAX-t norm relation equation constraint, Information Sciences, 181, 832-841, (2011) · Zbl 1211.90326 |

[61] | Stamou, G. B.; Tzafestas, S. G., Resolution of composite fuzzy relation equations based on Archimedean triangular norms, Fuzzy Sets and Systems, 120, 395-407, (2001) · Zbl 0979.03042 |

[62] | Wang, H. F.; Hsu, H. M., An alternative approach to the resolution of fuzzy relation equations, Fuzzy Sets and Systems, 45, 203-213, (1992) · Zbl 0761.04006 |

[63] | Wang, P. Z.; Sessa, S.; Di Nola, A.; Pedrycz, W., How many lower solutions does a fuzzy relation equation have?, BUSEFAL, 18, 67-74, (1984) · Zbl 0581.04001 |

[64] | Wang, X.-P.; Zhao, S., Solution sets of finite fuzzy relation equations with sup-inf composition over bounded Brouwerian lattices, Information Sciences, (2011) |

[65] | Wu, Y.-K.; Guu, S.-M., An efficient procedure for solving a fuzzy relational equation with MAX-Archimedean t-norm composition, IEEE Transactions on Fuzzy Systems, 16, 73-84, (2008) |

[66] | Wu, Y.-K., Optimization of fuzzy relational equations with MAX-av composition, Information Sciences, 177, 4216-4229, (2007) · Zbl 1140.90523 |

[67] | Xiong, Q.-Q.; Wang, X.-P., Solution sets of inf-α_{τ} fuzzy relational equations on complete Brouwerian lattices, Information Sciences, 177, 4757-4767, (2007) · Zbl 1129.03032 |

[68] | W.-L. Xu, Fuzzy relation equation, in: Reports on Beijing Fuzzy Mathematics Meeting, 1978. |

[69] | Xu, W.-L.; Wu, C.-F.; Cheng, W.-M., An algorithm to solve the MAX-MIN fuzzy relational equations, (Gupta, M.; Sanchez, E., Approximate reasoning in decision analysis, (1982), Amsterdam North-Holland), pp. 47-49 |

[70] | Yeh, C.-T., On the minimal solutions of MAX-MIN fuzzy relational equations, Fuzzy Sets and Systems, 159, 23-39, (2008) · Zbl 1176.03040 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.