Algorithm Engineering for Integral and Dynamic Problems

ISBN: 9789056993283 出版年：2001 页码：279 Rapanotti, Lucia CRC Press

LIST OF FIGURES LIST OF TABLES PREFACE ACKNOWLEDGEMENTS INTRODUCTION Algorithm Specialization Regular Array Synthesis From Affine to Integral Problems From Static to Dynamic Problems Outlines of the Book REGULAR ARRAY SYNTHESIS Basic Design Steps Euclidean Synthesis Regularization A Brief Survey Summary INTEGRAL RECURRENCE EQUATIONS Integral Data Dependencies Regularization Regularization and Affine Scheduling Summary DYNAMIC RECURRENCE EQUATIONS Inputs and Indexed Variables Dynamic Data Dependencies Dynamic Data Dependencies in Euclidean Synthesis Regularization Regularization and Affine Scheduling Summary CASE STUDIES Cyclic Reduction N Points FIR Filter for M-to-1 Decimation Knapsack Problem Gaussian Elimination with Partial Pivoting Summary CONCLUSIONS Further Work APPENDIX A: NOTATION APPENDIX B: GRAPH THEORY Graphs Connectivity Relations Graph Operations APPENDIX C: CONVEX SETS AND POLYHEDRA Combinations Affine Sets and Transformations Convex Sets Cones Recession Cone and Unboundedness Polyhedral Convex Sets Duality Separating Hyperplane Theorem Other Results APPENDIX D: ASPECTS OF LINEAR ALGEBRA Elementary Row Operations and Elementary Matrices Hermite Normal Form Integer Elementary Row Operations Unimodularity Echelon Form Linear Functional and Duality Annihilators Algorithmic Issues BIBLIOGRAPHY INDEX