2
$\begingroup$

I want to generalize the following to large N:

Solve[CharacteristicPolynomial[{{{Subscript[k, int] + Subscript[k, 
    0], -Subscript[k, int], 0, 0, 0, 0, 0, 0, 0, 0, 0, 
   0}, {-Subscript[k, int], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, ext], 0, 
   0, 0, 0, 0, 0, 0, 0, 0}, {0, -Subscript[k, ext], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, int], 0, 
   0, 0, 0, 0, 0, 0, 0}, {0, 0, -Subscript[k, int], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, ext], 0, 
   0, 0, 0, 0, 0, 0}, {0, 0, 0, -Subscript[k, ext], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, int], 0, 
   0, 0, 0, 0, 0}, {0, 0, 0, 0, -Subscript[k, int], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, ext], 0, 
   0, 0, 0, 0}, {0, 0, 0, 0, 0, -Subscript[k, ext], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, int], 0, 
   0, 0, 0}, {0, 0, 0, 0, 0, 0, -Subscript[k, int], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, ext], 0, 
   0, 0}, {0, 0, 0, 0, 0, 0, 0, -Subscript[k, ext], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, int], 0, 
   0}, {0, 0, 0, 0, 0, 0, 0, 0, -Subscript[k, int], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, ext], 
   0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, -Subscript[k, ext], 
   Subscript[k, ext] + Subscript[k, int], -Subscript[k, int]}, {0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, -Subscript[k, int], 
   Subscript[k, 0] + Subscript[k, int]}} - ω12^2*
  DiagonalMatrix[{m, m, m, m, m, m, m, m, m, m, m, 
    m}]}, ω12] == 0, ω12, Reals]

Please observe the pattern. The first row always (kint + k0,-kint, N - 2 zeros). The second row ( -kint, kext+kint, -kext, N - 3 zeros), third row (0, -kext, kext + kint, -kint, N -4 zeros), etc, finally the last row (N - 2 zeros, -kint, k0 + kint). I also want to put the resulting eigenvalues in a list.

$\endgroup$
4
$\begingroup$

I don't see any matrix multiplication to generalize, but I realize that it might be desireable to generate the tridiagonal matrix. One can employ SparseArray and Band for that as follows:

n = 12
A = SparseArray[
 {
  Band[{1, 1}] -> Join[{k[0] + k[int]},ConstantArray[k[ext] + k[int], n - 2], {k[0] + k[int]}],
  Band[{2, 1}] -> Riffle[
    ConstantArray[-k[int], Ceiling[(n - 1)/2]],
    ConstantArray[-k[ext], Floor[(n - 1)/2]]
    ],
  Band[{1, 2}] -> Riffle[
    ConstantArray[-k[int], Ceiling[(n - 1)/2]],
    ConstantArray[-k[ext], Floor[(n - 1)/2]]
    ]
  },
 {n, n}
 ];

The output A is a SparseArray; you can convert it to a conventional dense array with Normal[A]. For finding the eigenvalues of A, use Eigenvalues[A].

Remarks:

  • I replaced Subscript[k, int] etc. by k[int] because it is easier to read and because Subscript is a common source for unexpected behavior; search this site's history for a plethora of examples.

  • Don't expect the eigenvalues for large symbolic matrices to be in simple closed form. Usually, the symbolic complexity of the eigenvalue expressions grows rapidly with the size of the matrix.

$\endgroup$
3
$\begingroup$

Hello world!

Preword:

This is my first answer on MMA SE, and second on SE as a whole [I could not comment, but sought to provide an answer as my first toe-dip into SE], and while the owner has accepted Henrik Schumacher's answer, I am dealing with similar solution methods to systems of square (dense & antisymmetric) matrices of size N, so I feel compelled to deliver my findings thus far, and provide a (hopefully) more self-contained and complete answer (in the end).

Abstract

I will first identify the combination of problems presented, there being at least two, and then provide here my present collection of solutions to them, below. This is a working answer, and will be updated as I gain some insight to my methods thus far, through interaction with the SE community and my own development. Here, you will find related links and code that will prove to be useful for a wide-variety of Eigen-related solutions. This will be written in the framework of an unpublishable paper, as I am beginning to write the first of many academic texts, and this will also help me to collate my references and findings on possible solutions.

Introduction/Motivation

The problem of fast eigensystem solving of large numbers of large numerical matrices remains nontrivial, and has two main issues (with solutions) when considering speed-up and memory efficiency:

  1. P: Eigensystem is not inherently parallelizable, nor is there a current implementation of CUDAEigensystem within the Wolfram Language (I am compiling notes on this, and may tackle it at the WSS2019, if I am accepted, and will attempt it at home, if I am not). S: With some listable function, this function being some routine you've defined according to some variable, you can use something like

    `ParallelMap[Eigensystem[M[#]]&/@Nvars]`
    

    in order to achieve significant speed increases above non-parallelized implementations. This is likely not the best way, however our goal is to find the best self-contained solution we can, so this is, at least, a better option, and a good start.

  2. P: If your matrices are large enough, and are built through symbolic input and evaluation, you find significant improvements in timing through pre-compilation of your original matrix building function, and we can find any number of ways to do so. S: I will showcase a method of pure function compilation which is self-contained and a single line, one that I have not seen elsewhere, and was implemented due to my current level of understanding of compiling in C, and the need for a quick solution prior to conference proceedings:

    Export[NotebookDirectory[]<>"PureFunctionMatrix.wdx",ToExpression[StringReplace[ToString[UserDefinedMatrixBuildingFunction[a,b,c],InputForm],{"a"->"#1","b"->"#2","c"->"#3"}]<>"&"]];
    

Findings/References

It is imperative to mention that numerical computations of Eigensystem[] are preferred, and in some cases may be the only viable method with realistic runtime and memory consumption. Please see here:

SO References:

WHY YOU SHOULD AVOID SYMBOLICS IN EIGENSYSTEM:

SE References:

Numerical speed up of Eigen-evaluations:

The benefits of precompiling:

Related Reddit post encouraging the use of numerical inputs even if it is a MATLAB example:

Discussion & Conclusion

This is, by no means, a complete answer (yet) either, but it is necessary to identify that this question has several parts, each with a variety of solutions to be had. With the updates had recently, and those looming to be, it is helpful to provide a collated and up-to-date accounting of the solutions to the speed-up of large numbers of large numerical matrices. I will post this now, as it is, and will revisit this answer in a day or so when I have more free time. I must (should [need]) get to working with MMA, and will return to play soon thereafter. Thank you all for your time and immense levels of help and experience, I hope that this answer provides some valuable direction to all.

I am just now realizing that I did not directly address the pre-compiling question, but that should serve to be a fun venture after one is able to comb through these various references and suggestions. I may make some attempt at a solution in the future, however, if this serves to be a difficulty, Hamza.

Additional References

$\endgroup$
  • $\begingroup$ Could you explain more about #2 -- what it's doing and what you do with it? thanks! $\endgroup$ – Chris K May 8 at 17:42
  • $\begingroup$ @ChrisK Definitely! I haven't yet posted a question to post to further the method, but I will likely post this type of thing while I am at WSS19. For me, it was a way to turn any matrix, with blocks dependent on any number of variable and non variable parameters, into a pure function. (I really like these!) So; 1) Compile the large block matrix (something like 300x300 of 2 different 2x2 size blocks), then you can 2) ReplaceAll of the variables with the anonymous slotted variables. I think I redefined my original function after this, and found numeric compiling to be faster. However... 1/2 $\endgroup$ – CA Trevillian May 9 at 2:07
  • $\begingroup$ 2/2 you might have some function (like mine), which you do not want to share with your end user, or similar situation. (I'll share my original function and request advice this way, through SE, once I am to where I have submitted the paper written from it, and need assistance in finalizing the packaged demonstration I am building). I do think, however, that this pure functional package method would be father than pure numerical compiling (via internal WL functions) using some method of associations? I don't know if I can find the post(s) by @HenrikSchumacher, but iirc, it can provide a....(2/3) $\endgroup$ – CA Trevillian May 9 at 2:19
  • $\begingroup$ 3/3 method for faster variable assignment/numerical inputs (in a long series of these functions being compiled for a variety of numerical values). SO I found that you could just use assumptions to beat the time saved by precompiling in this manner, using inputs of the numerical or integer values which match the assumptions. BUT I have not done any coherent recording/tracking of my variety of methods in trying to solve my problem of needing to speedily compile ~10K matrices of 300x300 or larger. The first obvious thing was to remove time for repeated compiling. Numeric assumptions solved this. $\endgroup$ – CA Trevillian May 9 at 2:26
  • $\begingroup$ One more comment, honest! To sum: when you have to compile a matrix ~10K times, for one main value, you can remove the time needed to (symbolically) compile the matrix, by doing so via this purefunctionmatrix method. I know I am having issues in properly iterating what I (actually) did, or why, but this is, on the surface, a one-liner for making a purefunction matrix with anonymous variables instead of the symbolic ones. Anonymous assignment is faster than assigning variable values. But numeric inputs & assumptions beat these. I think I can (learn to)compile this in C and run even faster. $\endgroup$ – CA Trevillian May 9 at 2:34

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.