کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6416156 1631102 2016 37 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An efficient tree decomposition method for permanents and mixed discriminants
ترجمه فارسی عنوان
یک روش تجزیه و تحلیل درختان کارآمد برای تمایز دائمی و مخلوط
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
چکیده انگلیسی

We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays (tensors). We describe the sparsity structure of an array in terms of a graph, and we assume that its treewidth, denoted as ω, is small. Our algorithm requires O˜(n2ω) arithmetic operations to compute permanents, and O˜(n2+n3ω) for mixed discriminants and hyperdeterminants. We finally show that mixed volume computation continues to be hard under bounded treewidth assumptions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 493, 15 March 2016, Pages 45-81
نویسندگان
, ,