The methods of burst-error correction for cyclic (n, k) codes based on the mathematical theory of linear finite-state machines (LFSM) are considered. The algorihtm of sparse error burst correction of length no more th...
详细信息
ISBN:
(纸本)9781424439676
The methods of burst-error correction for cyclic (n, k) codes based on the mathematical theory of linear finite-state machines (LFSM) are considered. The algorihtm of sparse error burst correction of length no more than n - k/2, allowing to achieve k/2 times performance gain compared to with known methods is suggested. The algorihtm of full error burst correction of arbitrary length tau and complexity O(n x tau) based LFSM graphical models is suggested (tau = 1 divided by n - 1). The possibility of parallel search of the errors of various types is shown.
In this paper, we propose a weighted short-step primal-dual interior point algorithm for solving monotone linear complementarity problem (LCP). The algorithm uses at each interior point iteration a full-Newton step an...
详细信息
In this paper, we propose a weighted short-step primal-dual interior point algorithm for solving monotone linear complementarity problem (LCP). The algorithm uses at each interior point iteration a full-Newton step and the strategy of the central path to obtain an epsilon-approximate solution of LCP. This algorithm yields the best currently well-known theoretical complexity iteration bound, namely, O(root n log n/epsilon) which is as good as the bound for the linear optimization analogue. The implementation of the algorithm and the algorithm in Wang et al. (Fuzzy Inform Eng 54:479-487, 2009) is done followed by a comparison between these two obtained numerical results.
Several interior point algorithms have been proposed for solving nonlinear monotone complementarity problems. Some of them have polynomial worst-case complexity but have to confine to short steps, whereas some of the ...
详细信息
Several interior point algorithms have been proposed for solving nonlinear monotone complementarity problems. Some of them have polynomial worst-case complexity but have to confine to short steps, whereas some of the others can take long steps but no polynomial complexity is proven. This paper presents an algorithm which is both long-step and polynomial. In addition, the sequence generated by the algorithm, as well as the corresponding complementarity gap, converges quadratically. The proof of the polynomial complexity requires that the monotone mapping satisfies a scaled Lipschitz condition, while the quadratic rate of convergence is derived under the assumptions that the problem has a strictly complementary solution and that the Jacobian of the mapping satisfies certain regularity conditions
作者：
PAGER, DUNIV HAWAII
DEPT INFORMATION & COMP SCI2565 THE MALLHONOLULUHI 96822
In this paper it is shown that whatever the length function employed, the problem of finding the shortest program for a decision table with two (or more) entries is not recursively solvable (whereas for decision table...
详细信息
In this paper it is shown that whatever the length function employed, the problem of finding the shortest program for a decision table with two (or more) entries is not recursively solvable (whereas for decision tables with a single entry the problem is solvable for some length functions and unsolvable for others). Moreover, it is shown that there is a pair of finite sets of programs and a single entry E such that the shortest program for the decision table formed by adding a single additional entry to E is in all cases in one of the two sets, but it is undecidable in which. Some consequences of these results are then presented, such as showing that for a wide range of restrictions the results remain true, even when the repertoire of possible programs for a decision table is narrowed by only considering programs which meet certain restrictions.
The paper gives a complete justification of the modular algorithm for reducing matrices to the Hermitian normal form, which enables one to construct a new modular algorithm for reducing to the Smith normal form that m...
详细信息
The paper gives a complete justification of the modular algorithm for reducing matrices to the Hermitian normal form, which enables one to construct a new modular algorithm for reducing to the Smith normal form that may simultaneously calculate the left matrix of the transformations. The main term in the estimate of the number of operations is 2(n(3)log D), where.. is the size and D is the determinant (or a multiple of it) of the matrix under consideration.
In this paper, a weighted short-step primal-dual path-following interior-point algorithm for solving linear optimization (LO) is presented. The algorithm uses at each interior-point iteration a full-Newton step, thus ...
详细信息
In this paper, a weighted short-step primal-dual path-following interior-point algorithm for solving linear optimization (LO) is presented. The algorithm uses at each interior-point iteration a full-Newton step, thus no need to use line search, and the strategy of the central-path to obtain an epsilon-approximated solution of LO. We show that the algorithm yields the iteration bound, namely, O(root n log n/epsilon). This bound is currently the best iteration bound for LO. Finally, some numerical results are reported in order to analyze the efficiency of the proposed algorithm.
暂无评论