The front size of a matrix $A$ is the largest number of non-zeros below the diagonal in any column of its Cholesky factor. If $A$ is symmetric then the minimum front size of $A$ is equal to the treewidth of $G(A)$. Here $G(A)$ is an undirected graph with $A$ as its adjacency matrix. Hence, front size of symmetric matrix can be approximated by using the approximation algorithms of treewidth. The best known factor is $O(\sqrt{\log{n}})$.

I noticed that an approximation algorithm (to approximate Kelly-Width) in one of my recent papers, implies $O({\log}^{3/2}{n})$ approximation for front size of asymmetric matrices.

Minimizing front size is a fundamental problem and is very crucial in multi-frontal algorithms. I am wondering if there is an earlier approximation algorithm for front size of asymmetric matrices.

I will be surprised (and simultaneously excited) if the algorithm mentioned in my paper is the first approximation algorithm with non-trivial approximation factor.

Is there an approximation algorithm for the front size of asymmetric matrices, prior to our work ?



Your Answer

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