Start with a set of nodes (picture them as dots). Suppose there are

*n*nodes in all (say 3), numbered from 1 to*n*. Construct an*n*by*n*table (if there are 3 nodes, it will look like a blank tic-tac-toe board). Put a 1 in the entry in row*i*, column*j*to indicate that there is an edge*from*node*i**to*node*j*. (Edges can be pictured as arrows connecting the dots.)The result is called a

*directed graph*, “directed” because each edge has a starting and an ending node. (In the case of 3 nodes, the table will look like a finished game of tic-tac-toe, with 1s for Xs and 0s for Os.) The table is called the “adjacency matrix” of the graph.A

*sparse*matrix is a matrix most of whose entries are zero. A sparse adjacency matrix corresponds to a graph with rather few edges. Airlines don’t schedule direct flights between every pair of cities they serve; instead relatively few cities are joined directly, so that in most cases to get from one city to another you’ll have to go through a “hub”. The adjacency matrix that corresponds to the airline graph will be sparse.All this by way of introducing some striking images. A research group at AT&T (more research! less spying!) has put together a gallery of large graphs. The sparse matrices represented in the gallery come from the Sparse Matrix Collection at the University of Florida. The collection contains 1890 matrices from a wide range of projects: fluid dynamics, quantum chemistry, network analysis… The example below is described only as arising in connection with an optimization problem.

## Error

Comments allowed for friends only

Anonymous comments are disabled in this journal

Your reply will be screened