Algorithm Engineering for Integral and Dynamic Problems: 1st Edition (Hardback) book cover

Algorithm Engineering for Integral and Dynamic Problems

1st Edition

By Lucia Rapanotti

CRC Press

280 pages

Purchasing Options:$ = USD
Hardback: 9789056993283
pub: 2001-01-23
Currently out of stock
$145.00
x


FREE Standard Shipping!

Description

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 the criticism that they are applicable only to restricted classes of algorithms.

Algorithm Engineering for Integral and Dynamic Problems reviews the basic principles of regular array synthesis and shows how to extend its use into classes of algorithms traditionally viewed to be beyond its domain of application. The author discusses the transformation of the initial algorithm specification into a specification with data dependencies of increased regularity in order to obtain corresponding regular arrays by direct application of the standard mapping techniques. The book includes a review of the basic principles of regular array synthesis followed by applications of these techniques to well-known algorithms, concluding with numerous case studies to illustrate the methods.

Researchers and practitioners in algorithm engineering will find that this text significantly extends their understanding of the applications of regular array synthesis and regular array processors beyond the traditionally narrow field of relevance.

Table of Contents

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

Subject Categories

BISAC Subject Codes/Headings:
COM051300
COMPUTERS / Programming / Algorithms
MAT003000
MATHEMATICS / Applied