# Tag Info

15

If your graph is undirected (as I suspect), the matrix is symmetric, and you cannot do anything better than the Lanczsos algorithm (with selective reorthogonalization if necessary for stability). As the full spectrum consists of 100000 numbers, I giess you are mainly interested in the spectral density. To get an approximate spectral density, take the ...

11

Boost Graph Library and LEMON As Daniel mentions in his comprehensive answer, the most full-featured general C++ library is the Boost Graph Library. There is a new distributed-memory extension capable of doing some basic algorithms such as breadth-first and depth-first search, minimum spanning trees, and connected components search, but I am not very ...

8

Since you're already using C++ and your matrices are symmetric positive definite, I would perform an unpivoted $LDL^T$ factorization of $Q$ and also of $12I-Q-J$. Here I'm assuming that $12I-Q-J$ is also positive definite, otherwise the $LDL^T$ will require pivoting for numerical stability (it's also possible that even though it's not positive definite, ...

8

The short answer is no, there is not a standard format. But there are some common ones, like Gmsh for input/output and VTK for output. Before making a decision you need to find out what do you want to do. If you want to have your (small) program for a while, then you can pick the format that best suit to your taste and needs. If you are planning to change ...

6

When I was in the same position as you, I was very happy to find Knuth's Stanford Graphbase (SGB). He supplies not only a library for working with graphs, but also some data sets to play with. My favorite one was the 5-letter English words dataset. You can use your programming language of choice to generate an undirected graph where two words are neighbors ...

6

Arnold Neumaier's answer is discussed in more detail in section 3.2 of the paper "Approximating Spectral Densities of Large Matrices" by Lin Lin, Yousef Saad and Chao Yang (2016). Some other methods are also discussed but the numerical analysis at the end of the paper shows that the Lanczos method outperforms these alternatives.

5

Without some information about the construction of these $12\times 12$ positive definite real symmetric matrices, the suggestions to be made are of necessity fairly limited. I downloaded the Armadillo package from Sourceforge and took a look at the documentation. Try to improve performance of separately computing $\det(Q)$ and $\det(12I - Q - J)$, where $J$...

5

No need for any advanced books, the easiest to implement answer is: Use a DFS (http://en.wikipedia.org/wiki/Depth-first_search), and store the cumulative sum of each subtree in the stack. For example, a possible DFS traversal in your example is: A->B->D->I->J->E->C->F->G->H. After computing the cumulative sum of the child of a node, add this value to ...

5

The phrase "community detection" is loosely defined as partitioning the vertices of a graph into "communities" such that each has members more densely linked to one another than to members of other "communities". Our first task is to ascertain what this should mean in the case of a bipartite graph, which by definition consists of two "modes" such that ...

5

Perhaps, the Boost Graph Library is what you are looking for. It has a parser to read graphs specified in GraphViz's DOT format. While i don't really know about memory overhead, it does provide a variant for parallelization. Another graph library is LEMON but i don't really know it and if it has support for parallelization, it's not advertised. It's ...

5

I'd also like to mention STINGER, a dynamic graph data structure designed for parallelism. According to the website, it is designed for the following objectives: Portability: Algorithms written for STINGER can easily be translated/ported between multiple languages and frameworks Productivity: STINGER should provide a common abstract data structure such that ...

5

You don't need to check each pair of circles, so you can apply one of the neighour search algorithms. They restrict the distance calculations to the circles in the vicinity of each other by generating a list of potential neighbours based on a certain division of space. I would suggest to use the kd-tree method, which is efficient for circles with variable ...

4

Creating lattice (and other periodic) structures is a major issue in molecular simulations. Therefore, if you can translate your points into something that can be parsed by a viewer such as VMD or PyMol, you should be able to generate a view that can tell you if everything is working as expected. (This assumes, of course, that you build more than one ...

4

If you're ok with thinking about things that are not eigenvalues but functions that in some sense still tell you something about the spectrum, then I think you should check out some of the work by Mark Embree at Rice University.

4

If you have an array that stores the indices of the 3 neighbors of each cell, then you would only compute the midpoint of an edge of the neighbor cell has a higher index than the current cell, or if there is no neighbor at all. This way you have an easy tie breaker to decide which of the two cells is responsible for computing the edge midpoint.

4

75k x 75k double-precision entries is 45 gigabytes. That fits in memory, but barely; you need to be careful. The linear algebra routines in most languages rely on Lapack as a backend, which is a highly optimized linear algebra library written in Fortran. Most Lapack routines operate in-place: for instance, its QR routine xGEQRF does not allocate a second ...

3

The fairly simple Lloyd's algorithm can be used to achieve this. The essence of the algorithm is you start with a given tesselation defined by a set of points and a distance metric. The points are then moved to the centroids, allowing the tesselation and the areas to be recomputed. This iterative process is then repeated until the movement is sufficiently ...

3

In structural mechanics the number of eigenvalues of a matrix $K$ in a given range $(\alpha,\beta)$ is computed via the "Sturm sequence check", i. e. computing the $LDL^T$ factorizations of $K-\alpha I$ and $K-\beta I$ and counting the difference in the number of negative pivots. If you have reasonably large bins, can be applied to your problem, and should ...

3

Start with equal edge weight, so $A$ is a boolean matrix. Think about what happens when you apply $A$ to the $k$th column of the identity, $\mathbf e_k$. Are the nonzeros in $A \mathbf e_k$ upstream or downstream of node $k$? What happens when you apply $A$ again, $A(A \mathbf e_k)$? What happens when there are two length-2 paths from node $i$ to node $k$? ...

3

Use MatIncreaseOverlap() just like PCASM (additive Schwarz preconditioner) to get the overlapping region, then MatGetSubMatrices() (also like PCASM) to pull out the overlapping part of the matrix. For further technical discussion of implementation, we encourage you to subscribe to petsc-dev@mcs.anl.gov or just email petsc-maint@mcs.anl.gov.

3

There are a handful of common metrics when analyzing graphs and networks. Clustering coefficient: given a vertex $i$ in the graph and two neighbors $j$, $k$ of $i$, what are the odds that $j$ and $k$ are also connected? Analogy: knowing that Gertrude Stein and Ernest Hemingway are both friends of mine, what are the chances that they're friends with each ...

3

If different nodes have different costs, for example because different rows of your matrix have different numbers of nonzero entries, then you need to attach weights to each node of your graph. Graph partitioning algorithms such as METIS allow you to do this, creating partitions where it is not the number of nodes that are about equal between partitions, but ...

3

You might try either Gmsh's MSH file format or GAMBIT neutral file format.

3

There is actually a standard for this: ISO/TS 10303 (start with parts 1380 to 1386). Prior to being hijacked by ISO, this initiative, which began back in the 1980s, was known as PDES/STEP. See https://www.pdesinc.org/index.html But I don't believe anybody much uses it unless they are working in an environment where it is a mandatory requirement. A large ...

3

The number of file formats for FEM is ridiculous, partly due to the fact that every software package implemented its own format in the past. (From xkcd.) I've created meshio to alleviate the pain of converting between formats, so if you use any format supported by meshio, you should be able to easily make a switch in the future. Out of all formats I know, ...

3

Depth first search will put a node into the stack only once. The usual way to perform DFS involves marking a vertex as marked while pushing it into the stack and not pushing an already marked vertex again. A node will not enter the stack if and only if it is not part of the connected component involving the DFS start vertex. This only matters for graphs ...

3

Based on the provided description as well as the figure, you have an undirected graph with a single source and a sink at hand. The most famous option is to implement Dijkstra's algorithm. There are other options that are faster, but as long as your dealing with small instances and have no CPU time limit, I think you're good to go. In case you're interested, ...

3

If you have an algorithm that finds all cycles, then do the following steps: Take cycle 1, tag all edges that are part of it. Take cycle 2 and go through all edges that are part of it: If an edge is already tagged, then clearly that edge is part of another cycle and you don't have a cactus Otherwise, tag that edge Repeat with cycles 3...n

3

This is a fun question! After academic searches and Wiki came up bare, I dug through the source code of SageMath. That gets us to this: #A graph is called *cactus graph* if it is connected and every pair of simple cycles have at most one common vertex. # Special cases if self.order() < 4: #Number of vertices return True # Every cactus graph is ...

Only top voted, non community-wiki answers of a minimum length are eligible