کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6416156 | 1631102 | 2016 | 37 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An efficient tree decomposition method for permanents and mixed discriminants
ترجمه فارسی عنوان
یک روش تجزیه و تحلیل درختان کارآمد برای تمایز دائمی و مخلوط
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
چکیده انگلیسی
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
Journal: Linear Algebra and its Applications - Volume 493, 15 March 2016, Pages 45-81
نویسندگان
Diego Cifuentes, Pablo A. Parrilo,