1
$\begingroup$

I want to create a general formula for an $N \times N$ nearest neighbors Laplacian matrix such that I can write an mfile in MATLAB to compute the matrix for given $N$.

The nearest neighbors Laplacian matrix is of the below form

\begin{equation} L=\left[ \begin{array}{ccc} -2 & 1 & 0 & \cdots & 0 & 1\\ 1 & -2 & 1 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & 1 & -2 & 1\\ 1 & 0 & \cdots & 0 & 1 & -2\\ \end{array} \right]. \end{equation}

where the main diagonal elements are all $-2$ and we have two elements of $1$ before and after each element in the main diagonal.

Would appreciate any help...

$\endgroup$
2
$\begingroup$

I might be misreading what you have written as the $L$ matrix, but I believe you can use:

L = gallery('tridiag',ones(1,N-1),-2*ones(1,N),ones(1,N-1));

This will return the tridiaganol matrix in sparse form. You can wrap it in full() to convert it to a standard matrix. Then you can manually change the top and bottom corners to 1.

Let me know if this works or if I've misunderstood the form of L.

$\endgroup$
  • 1
    $\begingroup$ You can also set the corners within the sparse representation, if desired. $\endgroup$ – Ian Jun 8 '16 at 12:54
  • $\begingroup$ @Ian, absolutely, and that is necessary if the matrix is too large to create in full form. $\endgroup$ – David Jun 8 '16 at 12:58
0
$\begingroup$

Another way of doing this for full matrices is:

>> N=5;
>> L=diag(-2*ones(1,N),0)+diag(ones(1,N-1),1)+diag(ones(1,N-1),-1)
L =

  -2   1   0   0   0
   1  -2   1   0   0
   0   1  -2   1   0
   0   0   1  -2   1
   0   0   0   1  -2

>> L(1,N)=1
L =

  -2   1   0   0   1
   1  -2   1   0   0
   0   1  -2   1   0
   0   0   1  -2   1
   0   0   0   1  -2

>> L(N,1)=1
L =

  -2   1   0   0   1
   1  -2   1   0   0
   0   1  -2   1   0
   0   0   1  -2   1
   1   0   0   1  -2

>>
$\endgroup$
  • 1
    $\begingroup$ If N is large, this implementation takes appreciably longer. For example, N=10000, using the full(gallery) function takes on the order of 1e-2 seconds (on my machine), and this takes on the order of 1 second. Not sure if that matters or not. And for larger matrices, the gallery will let you generate it in sparse form as written, which may be convenient. $\endgroup$ – David Jun 8 '16 at 12:57
0
$\begingroup$

That symmetric matrix is almost a tridiagonal Toeplitz matrix. Hence,

r = [-2, 1, zeros(1,n-2)];
L = toeplitz(r);

Update now the northeast and southwest corners:

L(1,n) = 1;
L(n,1) = 1;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.