Algorithms for detecting separability of nonlinear mappings using computational graphs

A nonlinear mapping is called separable if it contains some of the variables in the separable form. Separability is a valuable property of nonliner mappings. Recently, many algorithms have been presented that exploit the separability to improve the computational efficiency of numerical algorithms. It has been shown that substantial improvement of computational complexity can be achieved by exploiting the separability. In order to apply these algorithms, it is necessary to detect which variable is contained in the separable form. However, such algorithms have not been presented in the past. When the nonlinear mapping is large and complicated, it is difficult to detect the separability by inspection. In this paper, some algorithms are proposed that detect the separability of nonlinear mappings automatically. For this purpose, the concept of computational graphs is introduced. It is shown that the proposed algorithms can detect the separability in execution time proportional to the number of edges of the computational graphs. [In Japanese.]