کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875620 | 1441976 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Duality and nonlinear graph Laplacians
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Specifically, we present an iterative algorithm for solving a class of nonlinear system of equations arising from a nonlinear generalization of the graph Laplacian in OË(k2mlogâ¡(kn/ϵ)) iterations, where k is a measure of nonlinearity, n is the number of variables, m is the number of nonzero entries in the generalized graph Laplacian L, ϵ is the solution accuracy and OË() neglects (non-leading) logarithmic terms. This algorithm is a natural nonlinear extension of the one in Kelner et al. (2013), which solves a linear Laplacian system of equations in nearly linear time. Unlike the linear case, in the nonlinear case each iteration takes OË(n) time so the total running time is OË(k2mnlogâ¡(kn/ϵ)). For sparse graphs with m=O(n) and fixed k this nonlinear algorithm is OË(n2logâ¡(n/ϵ)) which is slightly faster than standard methods for solving linear equations, which require approximately O(n2.38) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 713, 22 February 2018, Pages 21-30
Journal: Theoretical Computer Science - Volume 713, 22 February 2018, Pages 21-30
نویسندگان
Eric J. Friedman, Adam S. Landsberg,