I was wondering whether there is a closed formula for the eigenvalues and eigenvectors of the discretized Laplacian in (edit) $[0,1]^n$ with a uniform grid, using what I imagine is a $2n+1$ stencil.

Furthermore, I was wondering whether there is some existing material on how to create random weighted sparse (graph) Laplacian matrices from a random spectrum, that is, matrices $L$ with $L\mathbf{1}=0$, $L=L^t$, positive diagonal, negative off-diagonal entries and non-negative random spectrum.

My thoughts on creating $\Lambda$ myself were

lambda = rand(n,1); lambda(1) = 0;

then create $\chi$ and orthogonalize it using stable Gram-Schmidt

chi = randn(n,n); chi(:,1) = ones(n,1); chi = gram_schmidt(chi);



but it does not accomplish the sign conditions that I mentioned.

My interest is in having infinitesimal generators $Q$ for CTMC (edit: Continuous-Time Markov Chain) with number of states $n\gg 1000$ and available accurate diagonalization, so I thought the most studied case would be the discretized Laplacian. Any previous work on this?

Edit: thanks to lightxbulb in the comments, this works

function [Ltensor,FTtensor] = laplacian_matrix(nx,n)
  # pkg install -forge control, signals, communication
  # this function creates the periodic Laplacian matrix in the n-th hypercube,
  # as well as the matrix that diagonalizes it orthogonally, with size nx
  # h = 1/nx; I kind of not care about rescaling the Laplacian
  L = (diag(2*ones(nx,1)) - diag(ones(nx-1,1),1) - diag(ones(nx-1,1),-1));
  L(1,end) = -1; L(end,1) = -1;
  FT = dftmtx(nx);
  Ltensor = zeros(nx^n,nx^n); FTtensor = zeros(nx^n,nx^n);
  for i=1:n
    addL = 1; addFT = 1;
    for j=1:n
      if i==j
        addL = kron(addL,L);
        addL = kron(addL,eye(nx));
      addFT = kron(addFT,FT);
    Ltensor = Ltensor + addL;
    FTtensor = FTtensor + addFT; % this is clearly wrong I should only do this once but it still diagonalizes and I just realized right now
  FTtensor = FTtensor/(nx^n); % as I said this is wrong I will edit it later
  • $\begingroup$ This may perhaps work if you discretize a cube with a uniform mesh. But there is for sure no closed-form solution on arbitrary domains. $\endgroup$ Sep 12 at 14:27
  • $\begingroup$ @WolfgangBangerth yes, I was thinking of that case, my bad $\endgroup$
    – Aner
    Sep 12 at 14:43
  • $\begingroup$ CTMC = continuous-time Markov chain? $\endgroup$ Sep 12 at 20:19
  • 1
    $\begingroup$ It depends on the boundary conditions: periodic are diagonalized by DFT, reflecting by DCT, zero Dirichlet by DST. $\endgroup$
    – lightxbulb
    Sep 12 at 20:49
  • $\begingroup$ As @lightxbulb says, if you understand the 1d case with sines and cosines, then the 2d/3d case is just a tensor product. $\endgroup$ Sep 13 at 6:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.