Detail

A Note on Sparse Anti-Monge Matrices

In this talk we present a study on the multiplication of anti-Monge matrices. An anti-Monge matrix A, of size r ×c, is a generalization of a distribution matrix dA of a density matrix DA with non-negative values. Anti-Monge matrices arise often in optimization problems, for example as HSMs or DIST tables, that store scores between string S and all substrings of T. Two anti-Monge matrices A and B, of size (c = r’) ×c’, can be multiplied by using max instead of + in the standard matrix multiplication formula. Aggarwall et al. proposed the SMAWK algorithm, that determines all the row maximums of A in, optimal, O(cmax{1, log(r/c)}) time. Iterating the SMAWK algorithm we obtain a procedure to determine A ×B in O(r r’max{1, log(c’/r’)}) time. This solution however is not efficient when the matrices are sparse. For instance A is sparse if the number of non-zero entries deltaA of DA is o(rc). For example DIST tables have deltaA = O(n), where n = r = c = c’. This raised the question whether DIST tables can be multiplied in linear time, proposed as an open problem by Landau. Recently Tiskin proposed an, O(n logn) time, solution based on the fact that the density matrices of DIST tables and HSMs are permutations. However this algorithm cannot be applied to general, sparse, anti-Monge matrices. We present an algorithm to multiply sparse anti-Monge matrices in O(r logr’+ (r’ + (deltaAB + deltaA logr’ ) logr’) logc’) time and a data structure to represent these matrices. Hence we give a new solution for Landau’s problem. Our solution is very flexible, it can be used with simple score generalizations where previous algorithms require more space, are slower or inapplicable.