@article{Lohrey:2017aa,
    Abstract = {We study the complexity of algorithmic problems for matrices that are represented by multi-terminal decision diagrams (MTDD). These are a variant of ordered decision diagrams, where the terminal nodes are labeled with arbitrary elements of a semiring (instead of 0 and 1). A simple example shows that the product of two MTDD-represented matrices cannot be represented by an MTDD of polynomial size. To overcome this deficiency, we extended MTDDs to + MTDDs by allowing componentwise symbolic addition of variables (of the same dimension) in rules. It is shown that accessing an entry, equality checking, matrix multiplication, and other basic matrix operations can be solved in polynomial time for + MTDD-represented matrices. On the other hand, testing whether the determinant of a MTDD-represented matrix vanishes is PSPACE-complete, and the same problem is NP-complete for + MTDD-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is {\\#}P-complete.},
    Author = {Lohrey, Markus and Schmidt-Schau{\ss}, Manfred},
    Date = {2017/08/01},
    File = {Processing Succinct Matrices and Vectors - 14-csr.pdf},
    ISBN = {1433-0490},
    Journal = {Theory of Computing Systems},
    Number = {2},
    Pages = {322--351},
    Title = {Processing Succinct Matrices and Vectors},
    URL = {https://doi.org/10.1007/s00224-015-9666-9},
    Volume = {61},
    Year = {2017},
    bdsk-url-1 = {https://doi.org/10.1007/s00224-015-9666-9},
    date-added = {2023-09-21 08:17:41 +0200},
    date-modified = {2023-09-21 08:17:41 +0200},
    id = {Lohrey2017},
    doi = {10.1007/s00224-015-9666-9}
}

@article{Lohrey:2017aa, Abstract = {We study the complexity of algorithmic problems for matrices that are represented by multi-terminal decision diagrams (MTDD). These are a variant of ordered decision diagrams, where the terminal nodes are labeled with arbitrary elements of a semiring (instead of 0 and 1). A simple example shows that the product of two MTDD-represented matrices cannot be represented by an MTDD of polynomial size. To overcome this deficiency, we extended MTDDs to + MTDDs by allowing componentwise symbolic addition of variables (of the same dimension) in rules. It is shown that accessing an entry, equality checking, matrix multiplication, and other basic matrix operations can be solved in polynomial time for + MTDD-represented matrices. On the other hand, testing whether the determinant of a MTDD-represented matrix vanishes is PSPACE-complete, and the same problem is NP-complete for + MTDD-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is {\#}P-complete.}, Author = {Lohrey, Markus and Schmidt-Schau{\ss}, Manfred}, Date = {2017/08/01}, File = {Processing Succinct Matrices and Vectors - 14-csr.pdf}, ISBN = {1433-0490}, Journal = {Theory of Computing Systems}, Number = {2}, Pages = {322--351}, Title = {Processing Succinct Matrices and Vectors}, URL = {https://doi.org/10.1007/s00224-015-9666-9}, Volume = {61}, Year = {2017}, bdsk-url-1 = {https://doi.org/10.1007/s00224-015-9666-9}, date-added = {2023-09-21 08:17:41 +0200}, date-modified = {2023-09-21 08:17:41 +0200}, id = {Lohrey2017}, doi = {10.1007/s00224-015-9666-9} }