How to perform nested dissection online instead of reading from file?

[learning-chip]

Hi,

I found this repository from the paper A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity. Thanks for releasing the code.

I'd like to replicate the numerical results. However, the factor(A, nd, nd_loc) function call requires a known nested dissection data structure nd. In the unit test, the structure is read from a file that is not contained in this repo:

HierarchicalSolvers.jl/test/rungmres.jl

Lines 16 to 20 in 392b40d

	A, b, nd = read_problem("./test/poisson3d_p1_h16_nmax10.mat")
	nd, nd_loc = symfact!(nd)
	perm = postorder(nd)
	A = permute(A, perm, perm)
	nd = permuted!(nd, invperm(perm))

How can I make a valid nd object for an abitrary matrix A? Would the Metis Julia wrapper help? Thanks!

[bonevbs]

Hi,

yes you could use Metis to do so or you could create your own nested dissection. Are you trying to factorise your own matrix or do you just want to try it out on a given matrix?

If you want to solve your own problem (with geometric information) I would suggest computing your own nested dissection. It is basically just a binary tree which indicates interior and boundary degrees of freedom.

If you just want to try it out, you can use my generator scripts to generate test matrices. Those are in this repository here as I used some Matlab code to generate the matrices: nodal-dg-extension and nodal-dg. You can use GenMatrixPoisson2D to generate a Poisson matrix and the corresponding nested dissection, then load it using read_problem.

Let me know if it works :)

Fair word of caution - the library is mostly a proof of concept to prove the complexity of the method.

Boris

[learning-chip]

Are you trying to factorise your own matrix or do you just want to try it out on a given matrix?

Thanks for the reply. I'd like to try my own matrix generated from finite-element assembly. The FEM mesh is unstructured so it's hard to do geometric ND. The algebraic ND in METIS is more suitable. The question is how to convert the output of METIS.jl to match the NestedDissection data structure in your code.

You can use GenMatrixPoisson2D to generate a Poisson matrix and the corresponding nested dissection, then load it using read_problem.

Thanks but I have no MATLAB license😅. Could you upload a small generated file for testing purpose? Then I can follow its data structure and try adapting METIS's output to match that.

[learning-chip]

the library is mostly a proof of concept to prove the complexity of the method.

I am aware of that, and my interest here is indeed to verify the algorithm complexity instead of run time.

It's actually quite interesting that your paper states the linear complexity holds for 2D but not for 3D problems (Section 6.2. "Three-dimensional problems", "The overall cost to form the approximate factorization seems to scale as O (n^2)").

But in the Strumpack HSS paper, 3D helmholtz is said to have log-linear factorization complexity (Table 1), and "for the 3D problem, much more aggressive HSS compression can be used" (much larger tolerance ε for 3D in Table 3, 4).

[bonevbs]

That's interesting indeed. In our paper we couldn't go to large matrices as our code is single-node and we tested It only on matrices that fit in memory with 32GB RAM. So it could be that we haven't reached the asymptotic regime as the off-diagonal ranks in 3d were much larger. Strumpack is much more optimized as a whole so it could be that they observe the proper scaling. I would be interested in learning what you observe with your tests!

[bonevbs]

I have uploaded the largest (2d) example matrices Github allowed me to upload. If you would like bigger ones let me know :)

[bonevbs]

regarding Metis - I dimly recall that there was an option in Metis to extract Vertex Separators. You might want to use that to compute the boundary DOFs which nd assumes. Let me know if you have more questions.

[learning-chip]

I have uploaded the largest (2d) example matrices Github allowed me to upload.

Thanks! The data works with the rungmres.jl script.

Let me try METIS.jl then.