Algebraic path problem

An important driver which has influenced several of the subtasks in the array synthesis methodologies in this book is the solution of the algebraic path problem (APP) which is occurring frequently in mathematical equation solvers and in data analysis. This driver will be discussed in detail in chapter 3. Several crucial subtasks will be identified, and the results for several architectures optimized for the APP problem will be described. For many of these subtasks, a link will be made with the synthesis techniques and tools necessary to address these issues. 

Formal methods for solving the algebraic path problem ... 

A. Benaini, P. Quinton, Y. Robert, Y. Saouter, and B. Tourancheau. Synthesis of a new systolic architecture for the algebraic path problem. Science of Computer Programming, 1989. 

This chapter focuses on the architecture study for a basic algorithm kernel— the algebraic path problem (APP)— that we have been investigating during Nana. Our goal in this chapter is threefold ... 

A. Benaini and Y. Robert. Space-time-minimal systolic arrays for gaussian elimination and the algebraic path problem. Parallel Computing, 15, pages 211-225, 1990. 

J. M. Delosme. A parallel algorithm for the algebraic path problem. In M. Cosnard et al., editors, Parallel and Distributed Algorithms, pages 67-78. North Holland, 1989. 

S. Y. Kung and P. S. Lewis. An optimal systolic array for the algebraic path problem. IEEE Trans, on Computers, C-40, pages 100-105,1991. 

T. Risset and Y. Robert. Synthesis of processor arrays for the algebraic path problem unifying old results and deriving new architectures. Parallel Processing Letters, 1, pages 19-28, 1991. 

Y. Robert and D. Trystram. Systolic solution of the algebraic path problem. In W. Moore, A. McCabe, and R. Urquhart, editors. Systolic Arrays, pages 171-180. Adam Hilger, Bristol, 1987. 

G. Rote. A systolic array algorithm for the algebraic path problem (shortest paths matrix inversion). Computing, 34, pages 191-219, 1985. 

---