The OPTGRAPH Procedure

Eigenvector Problem

Subsections:

Eigenvector Problem for a Small Matrix with Dense Input
Eigenvector Problem for a Small Matrix with Sparse Input

For a given square matrix A, the eigenvectors of the matrix are those nonzero vectors that remain proportional to the original vector after being multiplied by A. That is, upon multiplication, an eigenvector changes magnitude, but not direction. The corresponding amount that the vector changes in magnitude is called the eigenvalue. Mathematically, a nonzero vector v and scalar $\lambda$ is an eigenvector/value pair if and only if it satisfies the equation $Av = \lambda v$ .

In PROC OPTGRAPH, you can calculate eigenvectors of a given matrix by invoking the EIGENVECTOR statement. The options for this statement are described in the section EIGENVECTOR Statement.

The EIGENVECTOR statement reports status information in a macro variable called _OPTGRAPH_EIGEN_. See the section Macro Variable _OPTGRAPH_EIGEN_ for more information about this macro variable.

Although the matrix is typically defined in the input data set specified in the DATA_MATRIX= option, it can also be presented in the form of a graph by using the DATA_LINKS= option. In this case, the graph is converted to the corresponding adjacency matrix. This conversion enables you to calculate the eigenvectors of very large matrices, since the data format for a graph is very sparse. Because of memory limitations, the matrix format is useful only for relatively small matrices. Because the matrix must be symmetric, the graph input format works only for undirected graphs.

The algorithm that PROC OPTGRAPH uses to solve the eigensystem is a variant of the Jacobi-Davidson algorithm (Sleijpen and van der Vorst 2000). This algorithm uses sparse computations for efficiency and is designed to find a small number of extremal eigenvectors. If you want to find all the eigenvectors and your matrix is relatively small, the best alternative is to use the dense solver in the IML procedure. (See the SAS/IML User's Guide.)

Eigenvector Problem for a Small Matrix with Dense Input

This section shows the calculation of the principal eigenvectors of a small matrix with the following dense input:

data MatrixSetIn;
   input col1-col5;
   datalines;
1 0 2 6 1
0 2 3 0 1
2 3 1 0 2
6 0 0 0 0
1 1 2 0 0
;

The following statements calculate the two algebraically largest eigenvalues for the matrix defined in the data set MatrixSetIn:

proc optgraph
   data_matrix    = MatrixSetIn;
   eigenvector
      eigenvalues = LA
      nEigen      = 2
      out         = EigenMatrixOut;
run;

For a matrix with n columns, and NEIGEN=m requested eigenpairs, the algebraically largest eigenvalue is given in the last observation ( $n+1$ ) of the column eigen_1. The corresponding eigenvector is given in the same column in observations 1 through n. The second largest is given in column eigen_2, and so on, up to column eigen_m.

In this case, the resulting data set EigenMatrixOut (shown in Figure 1.75) gives the two largest eigenvector and eigenvalue pairs in columns eigen_1 and eigen_2. The first five observations give the values of the eigenvectors (one for each column of the matrix), and the sixth observation gives the corresponding eigenvalue.

Figure 1.75: Eigenvector Problem for a Small Matrix with Dense Input

obs	eigen_1	eigen_2
1	0.65778	0.32280
2	0.26459	-0.64125
3	0.40078	-0.49082
4	0.53174	0.40988
5	0.23227	-0.27513
.	7.42209	4.72527

Eigenvector Problem for a Small Matrix with Sparse Input

This section shows the use of a sparse input format for the eigenvector problem. The following statements define the same matrix that is used in the section Eigenvector Problem for a Small Matrix with Dense Input, but they represent it sparsely in the form of graph links:

data LinkSetIn;
   input from to weight;
   datalines;
0 0 1
0 2 2
0 3 6
0 4 1
1 1 2
1 2 3
1 4 1
2 2 1
2 4 2
;

Notice that there are self links $i \rightarrow i$ . These correspond to the diagonal entries in the matrix that is defined in the data set MatrixSetIn. By default, PROC OPTGRAPH ignores self links. Therefore, in the sparse format, you must use the INCLUDE_SELFLINK option to match the dense matrix from the section Eigenvector Problem for a Small Matrix with Dense Input. Now you can calculate the same eigenvectors using sparse input as follows:

proc optgraph
   include_selflink
   data_links     = LinkSetIn;
   eigenvector
      eigenvalues = LA
      nEigen      = 2
      out         = EigenLinksOut;
run;

The output is shown in Figure 1.76.

Figure 1.76: Eigenvector Problem for a Small Matrix with Sparse Input

node	eigen_1	eigen_2
0	0.65778	0.32280
2	0.40078	-0.49082
3	0.53174	0.40988
4	0.23227	-0.27513
1	0.26459	-0.64125
.	7.42209	4.72527