An efficient algorithm to determine the image of a parallelepiped under a linear transformation

ABSTRACT

An efficient algorithm to determine the image of a parallelepiped under a linear transformation is presented. The work was motivated by certain problems in the testing of analog integrated circuits. The method is based on specifying the boundary hyperplanes that define the image polytope and is of polynomial complexity in n (the dimension of the parallelepiped), for a fixed value of the dimension of the range of the linear transformation. The algorithm has been implemented using library routines from LINPACK.

REFERENCES

• 1: L.S. Milor and V. Visvanathan, "Preliminary. Studies on Analog Fault Signature Calculation" manuscript in preparation.
• 2: V. Visvanathan, E. Szeto and A. Tits, "A Robust Simulation-Before-Test Technique for DC Analog Fault Diagnosis," Procceedings of the International Symposium of Circuits and Systems (iSCAS), Montreal, Canada, 1984, pp. 689-692.
• 3: S. Liu and K. Singhal, "A Statistical Mosfet Model," Proceedings of the International Conference on Computer-Aided Design, San Jose, California, 1985, pp. 78-80.
• 4: W.C. Wu, "A Robust Simulation-Before-Test Technique for Nonlinear Analog Fault Diagnosis," M.S. Thesis, Electrical Engineering Department University of Maryland, 1984.
• 5: D.T. Lee and F.P. Preparata, "Computational Geometry - A Survey," IEEE Transactions on Computers, vol. C-33, no. 12, December 1984, pp. 1072-1101.
• 6: R.T. Rockafellar, "Convex Analysis,' Princeton University Press, 1970.
• 7: M. Spivak, "Calculus on Manifolds," W.A.Benjamin, Inc., New York, 1965.
• 8: S. Liu, K. Singhal and V. Visvanathan, "CENTER/ADVICE: A CAD System for Circuit Design Optimization,' manuscript in preparation.
• 9: L.W. Nagel, "ADVICE for Circuit Simulation,* Proc. ISCAS Houston, Texas, 1980.
• 10: J.J. Dongarra et.al., *LINPACK User's Guide," SIAM, Philadelphia 1979.
• 11: A.L. Tits, Private Communication.
• 12: E. Grosse, Private Communication.
• 13: Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
• 14: G. Swart, "Finding the Convex Hull Facet by Facet," Journal of Algorithms, vol. 6 no. 1, March 1985, pp. 17-48.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE

      Nouns: LINPACK

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Performance, Theory, Verification