On-Line Geometric Modeling Notes

Eigenvalues and Eigenvectors
of the Refinement Matrix

Overview

The basic operation in the development of subdivision curves is the refinement procedure. In the cubic case, the points of the refinement can be specified as vertex and edge points and the refinement procedure can be specified by a matrix operation. In this case the refinement matrix A is defined to be

In these notes, we develop the eigenvalues and eigenvectors of the refinement matrix which play an important role in the analysis of subdivision curves. This matrix is also diagonalizable and we use the eigenvalues and eigenvectors to calculate this diagonal decomposition. Finally, the diagonal decomposition allows an easy calculation of the inverse of the matrix.

For a postscript version of these notes look here

The Eigenvalues of the Refinement Matrix

One of the eigenvalues is easy to calculate. Since the rows of A all sum to one, we have

and so 1 is an eigenvalue of A, with corresponding eigenvector . The other eigenvalues can be calculated from the characteristic polynomial and turn out to be and .

The (right) eigenvectors for the eigenvalues can be calculated to be

respectively, and in a similar fashion the left eigenvectors turn out to be

Diagonalization of the Matrix

We will let L be the matrix whose rows are the left eigenvectors of A,

and R be the matrix whose columns are the right eigenvectors of A,

noting that Then since the matrix A has 3 distinct eigenvalues, it is diagonalizable [1] and can be written as

where is the diagonal matrix whose diagonal elements are the eigenvalues of A.

The Inverse of the Refinement Matrix

Since the refinement matrix can be written as , it is easy to generate the inverse of A.

since . The matrix is just

The inverse of A then works out to be

Summary

The eigenvalues and eigenvectors of the refinement matrix are straightforward to calculate. Since this matrix is well conditioned it can be diagonalized and written in form which will be very useful when analyzing subdivision curves.

References

1

GOLUB, G. H., AND VAN LOAN, C. F. Matrix Computations, 2nd ed. Johns Hopkins University Press, 1989.

2

HALSTEAD, M., KASS, M., AND DEROSE, T. Efficient, fair interpolation using Catmull-Clark surfaces. In Computer Graphics (SIGGRAPH '93 Proceedings) (Aug. 1993), J. T. Kajiya, Ed., vol. 27, pp. 35-44.

This document maintained by Ken Joy Comments to the Author All contents copyright (c) 1996, 1997 Computer Science Department, University of California, Davis All rights reserved.