Universal algorithms for solving the matrix Bellman equations over semirings

DOI10.1007/S00500-013-1027-5MaRDI QIDQ889976zbMATH OpenOpenAlexFDO

Authors A. Ya. Rodionov, S. N. Sergeev, Grigori L. Litvinov, Andrei Sobolevski

Publication date 9 November 2015

Published in Soft Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5011

zbMATH Keywords

semiringmatrix Bellman equationtropical and idempotent semiringsuniversal algorithms

Mathematics Subject Classification ID

Max-plus and related algebras (15A80) Computational aspects of associative rings (general theory) (16Z05) Matrix equations and identities (15A24) Semirings (16Y60)

Abstract: This paper is a survey on universal algorithms for solving the matrix Bellman equations over semirings and especially tropical and idempotent semirings. However, original algorithms are also presented. Some applications and software implementations are discussed.

Recommendations

• Exact interval solutions of the discrete Bellman equation, and the polynomial complexity of problems in interval idempotent linear algebra.
• Methods and applications of \((\max,+)\) linear algebra
• scientific article; zbMATH DE number 1136259
• Idempotent/tropical analysis, the Hamilton-Jacobi and Bellman equations
• Universal numerical algorithms and their software implementation

Cites work

• scientific article; zbMATH DE number 3649911 (Why is no real title available?)
• scientific article; zbMATH DE number 3880009 (Why is no real title available?)
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 5309928 (Why is no real title available?)
• scientific article; zbMATH DE number 4072419 (Why is no real title available?)
• scientific article; zbMATH DE number 4073530 (Why is no real title available?)
• scientific article; zbMATH DE number 3711960 (Why is no real title available?)
• scientific article; zbMATH DE number 3783030 (Why is no real title available?)
• scientific article; zbMATH DE number 108422 (Why is no real title available?)
• scientific article; zbMATH DE number 3511882 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1012624 (Why is no real title available?)
• scientific article; zbMATH DE number 1032022 (Why is no real title available?)
• scientific article; zbMATH DE number 1163658 (Why is no real title available?)
• scientific article; zbMATH DE number 1944711 (Why is no real title available?)
• scientific article; zbMATH DE number 1358710 (Why is no real title available?)
• A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)
• Algebraic structures for transitive closure
• An Algebra for Network Routing Problems
• Computational complexity and feasibility of data processing and interval computations
• Computational methods of linear algebra
• Control solvability of interval systems of max-separable linear equations
• From the sixteenth Hilbert problem to tropical geometry
• Graphs, dioids and semirings. New models and algorithms.
• Idempotent functional analysis: An algebraic approach
• Idempotent interval analysis and optimization problems
• Idempotent mathematics: a correspondence principle and its applications to computing
• Interval Methods for Systems of Equations
• Interval arithmetic and linear algebra over idempotent semirings.
• Interval systems of max-separable linear equations
• Interval systems of max-separable linear equations
• Interval systems over idempotent semiring
• Linear Optimization Problems with Inexact Data
• Max-linear systems. Theory and algorithms.
• Minimax algebra
• On a new principle of superposition for optimization problems
• Optimale Lösung von Intervallgleichungssystemen
• Regular Algebra Applied to Path-finding Problems
• Tropical geometry and its applications
• Universal numerical algorithms and their software implementation
• Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings

Cited in

(8)

• Ideal basis in constructions defined by directed graphs
• Exact interval solutions of the discrete Bellman equation, and the polynomial complexity of problems in interval idempotent linear algebra.
• The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields
• Artificial Intelligence and Symbolic Computation
• A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +)
• A velocity-combined local best particle swarm optimization algorithm for nonlinear equations
• On pseudo-inverses of matrices and their characteristic polynomials in supertropical algebra
• Universal numerical algorithms and their software implementation

This page was built for publication: Universal algorithms for solving the matrix Bellman equations over semirings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q889976)