1st Edition
Algorithm Engineering for Integral and Dynamic Problems
By Lucia Rapanotti
Copyright 2001
280 Pages
by
CRC Press
280 Pages
by
CRC Press
Also available as eBook on:
Algorithm engineering allows computer engineers to produce a computational machine that will execute an algorithm as efficiently and cost-effectively as possible given a set of constraints, such as minimal performance or the availability of technology. Addressing algorithm engineering in a parallel setting, regular array syntheses offer powerful computation and embody best practice, but often face... Read more
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
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
Biography
Lucia Rapanotti
