Skip to main content
13 votes
Accepted

Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?

BLAS may not have a function to compute what you are asking for, but the product $$ Y_N = A^TY_AA + B^T Y_B B $$ means that the entries $(Y_N)_{ij}$ are defined by $$ (Y_N)_{ij} = \sum_{k,l} (A^T)...
Wolfgang Bangerth's user avatar
9 votes

What is a common file/data format for a mesh (for FEM)?

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 ...
nicoguaro's user avatar
  • 8,524
6 votes

Approximate spectrum of a large matrix

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 ...
A. Van Werde's user avatar
5 votes

Factorize laplacian in terms of first derivative matrix

It is sufficient if you consider a $D$ that uses forward or backward differences with reflecting boundaries: \begin{equation} D_f = \frac{1}{h}\begin{bmatrix} -1 & 1 & & \\ & \ddots &...
lightxbulb's user avatar
  • 2,197
5 votes
Accepted

Efficient algorithm to decide if a graph is a cactus?

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: ...
Richard's user avatar
  • 3,971
5 votes
Accepted

Find connected circles

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 ...
BalazsToth's user avatar
5 votes
Accepted

Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices

Let's take an $n\times n$ mesh (with $N=n^2$ unknowns) and think about whether you can enumerate them in such a way that you end up with a bandwidth less than $m=n=\sqrt{N}$? You get this bandwidth ...
Wolfgang Bangerth's user avatar
5 votes

Computing the Fiedler vector of a large, sparse graph

Disclosure: This is my master's supervisor's work, he and his co-authors are pretty well-known in the field. TRACEMIN-Fiedler is a parallel algorithm to compute the Fiedler vector of large graphs ...
Abdullah Ali Sivas's user avatar
4 votes

Moore-Penrose pseudoinverse of singular rank degenerate matrix

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 ...
Federico Poloni's user avatar
4 votes

Efficient algorithm to decide if a graph is a cactus?

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 ...
Wolfgang Bangerth's user avatar
4 votes

What is an instance (precisely) in computational complexity?

Pragmatically, an instance just means an input/output pair of an algorithm. I think a better example of a reduction would be transforming multiplication into repeated addition. For example, the ...
rchilton1980's user avatar
  • 4,936
4 votes

Problems on the algebraic theory of sparse matrices

your question is too general. It is very to hard to give specific advice. I will suggest you two books that you can use as first references, but they may not help much in terms of GPU computing for ...
Abdullah Ali Sivas's user avatar
3 votes
Accepted

Which optimization method can be used to do the following?

Despite my comment, I think you can find $\tilde{D}$ that contains the noise term as well. You have this equation: $$-M^{T} \tilde{D} M \phi(t) = -M^{T} D M \phi(t) + W(t)$$ Where $W(t)$ is the ...
Mithridates the Great's user avatar
3 votes

Finding a shortest path in a graph

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 ...
Ehsan's user avatar
  • 151
3 votes

Factorize laplacian in terms of first derivative matrix

@lightxbulb's answer gives the correct factorization already, but since you mention failed attempts with the Cholesky factorization, let me describe a method to discover the factorization numerically, ...
Federico Poloni's user avatar
3 votes
Accepted

Software for finding a minimum vertex cover for a hypergraph

I usually use SageMath for research work connected with graphs. However, I was not able to find there a ready-made algorithm to find a minimum vertex cover for a hypergraph (see subsection with the ...
Anton Menshov's user avatar
  • 8,672
3 votes
Accepted

Can a Depth first traversal of a graph visit node more than once?

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 ...
Raziman T V's user avatar
3 votes

What is a common file/data format for a mesh (for FEM)?

You might try either Gmsh's MSH file format or GAMBIT neutral file format.
Wes's user avatar
  • 270
3 votes

What is a common file/data format for a mesh (for FEM)?

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 ...
Nico Schlömer's user avatar
3 votes

What is a common file/data format for a mesh (for FEM)?

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:...
alephzero's user avatar
  • 311
2 votes

PageRank using Inverse Iteration Method by Cleve Moler

The MATLAB code that you've computed finds the eigenvector of $A$ associated with the eigenvalue 1. We know for this particular problem that $A$ has 1 as an eigenvalue- this can be shown using the ...
Brian Borchers's user avatar
2 votes

Hypergraph matching -> adjacency matrix?

Edges are represented as sets of vertices. With classical graphs, an edge can be represented by the set containing its 2 endpoints. With hypergraphs, they are represented by a set containing more than ...
jcm69's user avatar
  • 121
2 votes
Accepted

Moore-Penrose pseudoinverse of singular rank degenerate matrix

Although I'm unfamiliar with "distance metrics", there's no shortage of information about graph laplacians on the web because of their practical applicability to matrix reordering and classification/...
rchilton1980's user avatar
  • 4,936
2 votes
Accepted

What is an instance (precisely) in computational complexity?

When considering a problem in a Computational Complexity context, an instance for the problem is just an input to the problem encoded in a manner that works with the underlying model of computation. ...
spektr's user avatar
  • 4,258
2 votes
Accepted

Find shortest path around a cylinder represented by 3d triangular mesh

OK, after thinking about it for a while, I came up with an answer. Step 1: Find the caps of the cylinder, in other words two closed disjoint paths along the graph's borders. Step 2: Find a path ...
iliar's user avatar
  • 253
2 votes

How to reorder/cluster adjacency matrix to maximize the interaction along the super diagonal?

As far as I understand, you are looking for a family of algorithms that are used to reorder sparse matrices. Usually, it is used to reduce fill-in during sparse factorization; however, it's certainly ...
Anton Menshov's user avatar
  • 8,672
2 votes
Accepted

Newman algorithm yielding different result to what is given in his paper

It's a bit late, but I have a very simple answer: there is nothing wrong with the code I was simply missing the extra optimisation that Newman recommends in his paper. The results are perfectly in-...
daviegravee's user avatar
2 votes

Developing a meshfree contouring algorithm

Maybe this is not a full answer to your question. However, I am currently developing my own unstructured mesh generator and found this toolbox quite helpful. Perhaps there are some algorithms which ...
ConvexHull's user avatar
  • 1,379
2 votes

Developing a meshfree contouring algorithm

The following paper does a decent job of answering my question: D. H. McLain, Drawing Contours from Arbitrary Data Points, The Computer Journal, Volume 17, Issue 4, November 1974, Pages 318–324, ...
IPribec's user avatar
  • 617
2 votes

Does computing all shortest paths in a simple graph result in a complete graph that follows a metric?

I mean I think you clearly showed the graph $G$ can induce a metric, namely define $d_G(u,v)$ as the shortest path from $u \in V(G)$ to $v \in V(G)$ and you can readily show the three properties you ...
spektr's user avatar
  • 4,258

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