This letter presents a method for solving several linear equations in max-plus algebra. The essential part of these equations is reduced to constraint satisfaction problems compatible with mixed integer programming. This method is flexible, compared with optimization methods, and suitable for scheduling of certain discrete event systems.

This paper reports on the image compression tolerability and high implementability of a novel proposed watermarking method that uses a morphological wavelet transform based on max-plus algebra. This algorithm is suitable for embedded low-power processors in mobile devices. For objective and unified evaluation of the capability of the proposed watermarking algorithm, we focus attention on a watermarking contest presented by the IHC, which belongs to the IEICE and investigate the image quality and tolerance against JPEG compression attack. During experiments for this contest, six benchmark images processed by the proposed watermarking is done to reduce the file size of original images to 1/10, 1/20, or less, and the error rate of embedding data is reduced to 0%. Thus, the embedded data can be completely extracted. The PSNR value is up to 54.66dB in these experiments. Furthermore, when the smallest image size is attained 0.49MB and the PSNR value become about 52dB, the proposed algorithm maintains very high quality with an error rate of 0%. Additionally, the processing time of the proposed watermarking can realize about 416.4 and 4.6 times faster than that of DCT and HWT on the ARM processor, respectively. As a result, the proposed watermarking method achieves effective processing capability for mobile processors.

This research aims to accelerate the computation module in max-plus algebra using CUDA technology on graphics processing units (GPUs) designed for high-performance computing. Our target is the Kleene star of a weighted adjacency matrix for directed acyclic graphs (DAGs). Using a inexpensive GPU card for our experiments, we obtained more than a 16-fold speedup compared with an Athlon 64 X2.

This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband EngineTM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.

This research proposes efficient calculation methods for the transition matrices in discrete event systems, where the adjacency matrices are represented by directed acyclic graphs. The essence of the research focuses on obtaining the Kleene Star of an adjacency matrix. Previous studies have proposed methods for calculating the longest paths focusing on destination nodes. However, in these methods the chosen algorithm depends on whether the adjacency matrix is sparse or dense. In contrast, this research calculates the longest paths focusing on source nodes. The proposed methods are more efficient than the previous ones, and are attractive in that the efficiency is not affected by the density of the adjacency matrix.

This paper examines the properties of the greatest subsolution for linear equations in the max-plus algebra. The greatest subsolution is a relaxed solution of the linear equations, and gives a unified and reasonable solution whether there exists a strict solution or not. Accordingly, it forms part of a key algorithm for deriving a control law in the field of controller design, and some effective controllers based on the greatest subsolution have been proposed. However, there remain several issues to be discussed regarding the properties of the greatest subsolution. Hence, the main focus of this paper is on the following fundamental properties: 1) Formulation as an optimization problem, 2) Uniqueness of the greatest subsolution, 3) Necessary and sufficient condition for the correspondence of the greatest subsolution with the strict solution. These results could provide flexibility of the controller design based on the greatest subsolution, and facilitate the performance evaluation of the controller. Finally, the uniqueness of the strict solution of the linear equations is examined, and it is confirmed through illustrative examples.