دانلود مقاله ISI انگلیسی شماره 79102
عنوان فارسی مقاله

یک الگوریتم سریع برای محاسبات ماتریس پراکنده مربوط به معکوس.

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79102 2013 31 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A fast algorithm for sparse matrix computations related to inversion
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Computational Physics, Volume 242, 1 June 2013, Pages 915–945

کلمات کلیدی
تشریح تو در تو - تابع گرین؛ NEGF؛ تجزیه؛ حذف فیلتر؛ ماتریس پراکنده؛ معکوس؛ درخت حذف
پیش نمایش مقاله
پیش نمایش مقاله یک الگوریتم سریع برای محاسبات ماتریس پراکنده مربوط به معکوس.

چکیده انگلیسی

We have developed a fast algorithm for computing certain entries of the inverse of a sparse matrix. Such computations are critical to many applications, such as the calculation of non-equilibrium Green’s functions GrGr and G<G< for nano-devices. The FIND (Fast Inverse using Nested Dissection) algorithm is optimal in the big-O sense. However, in practice, FIND suffers from two problems due to the width-2 separators used by its partitioning scheme. One problem is the presence of a large constant factor in the computational cost of FIND. The other problem is that the partitioning scheme used by FIND is incompatible with most existing partitioning methods and libraries for nested dissection, which all use width-1 separators. Our new algorithm resolves these problems by thoroughly decomposing the computation process such that width-1 separators can be used, resulting in a significant speedup over FIND for realistic devices — up to twelve-fold in simulation. The new algorithm also has the added advantage that desired off-diagonal entries can be computed for free. Consequently, our algorithm is faster than the current state-of-the-art recursive methods for meshes of any size. Furthermore, the framework used in the analysis of our algorithm is the first attempt to explicitly apply the widely-used relationship between mesh nodes and matrix computations to the problem of multiple eliminations with reuse of intermediate results. This framework makes our algorithm easier to generalize, and also easier to compare against other methods related to elimination trees. Finally, our accuracy analysis shows that the algorithms that require back-substitution are subject to significant extra round-off errors, which become extremely large even for some well-conditioned matrices or matrices with only moderately large condition numbers. When compared to these back-substitution algorithms, our algorithm is generally a few orders of magnitude more accurate, and our produced round-off errors stay at a reasonable level.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.