Search

In this paper, two new algorithms for computing the Weighted Moore–Penrose inverse A M , N † of a general matrix A for weights M and N which are based on elementary row and column operations on two appropriate block partitioned matrices are introduced and investigated. The computational complexity of the introduced two algorithms is analyzed in detail. These two algorithms proposed in this paper are always faster than those in Sheng and Chen (2013) and Ji (2014), respectively, by comparing their computational complexities. In the end, an example is presented to demonstrate the two new algorithms. [ABSTRACT FROM AUTHOR]

Kernel ridge regression (KRR) is a popular scheme for non-linear non-parametric learning. However, existing implementations of KRR require that all the data is stored in the main memory, which severely limits the use of KRR in contexts where data size far exceeds the memory size. Such applications are increasingly common in data mining, bioinformatics, and control. A powerful paradigm for computing on data sets that are too large for memory is the streaming model of computation , where we process one data sample at a time, discarding each sample before moving on to the next one. In this paper, we propose StreaMRAK - a streaming version of KRR. StreaMRAK improves on existing KRR schemes by dividing the problem into several levels of resolution, which allows continual refinement to the predictions. The algorithm reduces the memory requirement by continuously and efficiently integrating new samples into the training model. With a novel sub-sampling scheme, StreaMRAK reduces memory and computational complexities by creating a sketch of the original data, where the sub-sampling density is adapted to the bandwidth of the kernel and the local dimensionality of the data. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum. The results show that the proposed algorithm is fast and accurate. [ABSTRACT FROM AUTHOR]

In many mathematical models of physical phenomenons and engineering fields, such as electrical circuits or mechanical multibody systems, which generate the differential algebraic equations (DAEs) systems naturally. In general, the feature of DAEs is a sparse large scale system of fully nonlinear and high index. To make use of its sparsity, this paper provides a simple and efficient algorithm for index reduction of large scale DAEs system. We exploit the shortest augmenting path algorithm for finding maximum value transversal (MVT) as well as block triangular forms (BTFs). We also present the extended signature matrix method with the block fixed point iteration and its complexity results. Furthermore, a range of nontrivial problems are demonstrated by our algorithm. [ABSTRACT FROM AUTHOR]

This paper describes a practical simulation-based algorithm, which we call the Stochastic Grid Bundling Method (SGBM) for pricing multi-dimensional Bermudan (i.e. discretely exercisable) options. The method generates a direct estimator of the option price, an optimal early-exercise policy as well as a lower bound value for the option price. An advantage of SGBM is that the method can be used for fast approximation of the Greeks (i.e., derivatives with respect to the underlying spot prices, such as delta, gamma, etc.) for Bermudan-style options. Computational results for various multi-dimensional Bermudan options demonstrate the simplicity and efficiency of the algorithm proposed. [ABSTRACT FROM AUTHOR]

Scott (1970) [11] introduced qualitative fixed point techniques as a suitable mathematical tool for program verification. Inspired by the fact that the Scott mathematical tools do not include metric implements, Matthews (1994) [8] introduced the concept of partial metric space with the aim of reconciling the Scott fixed point techniques with metric spaces and proved a fixed point theorem for self-mappings in partial metric spaces providing, thus, quantitative techniques useful, in the spirit of Scott, in denotational semantics. Schellekens (1995) [10] showed that the original Scott ideas can be also applied to asymptotic complexity analysis of algorithms via quantitative fixed point techniques for self-mappings in quasi-metric spaces. Later on Cerdà-Uguet et al. (2012) [3] showed that, contrarily to the case of Matthews partial metric spaces, partial quasi-metrics are useful for modeling the algorithmic complexity by means of quantitative fixed point techniques that preserve the Scott ideas and Schellekens techniques concurrently. In the present paper, we focus our efforts on developing a quantitative fixed point technique, based on partial quasi-metric spaces, that allows us to provide a suitable mathematical tool for program verification and complexity analysis simultaneously and, in addition, preserves the Scott ideas and the essence of Matthews and Schellekens techniques. Moreover, we show its applicability to discuss the running time of computing an algorithm using a recursive denotational specification and the meaning of such an specification. [ABSTRACT FROM AUTHOR]

Arsham ever described a new phase 1 simplex-type algorithm which allegedly obviates the use of artificial variables. Soon after, Enge and Huhn gave a counterexample, in which Arsham’s algorithm declares the infeasibility of a feasible problem. For this reason, this paper proposes an improvement of Arsham’s algorithm to make it work well, which is searching for the nonbasic variables into the basic variable set (BVS) column by column in only one pivot sequence from beginning to end in order to decrease computational time spent by many repeated searching sequences after each iteration. Next, when the BVS is complete, the phase 1 algorithm ends with a feasible basic solution; otherwise, two variants are presented to pivot the artificial variables out of the basis. The idea of variant 1 is making all artificial variables in basis minimized in turn while maintaining the BVS feasible in the pivoting process. In variant 2, the objective is to minimize the sum of all artificial variables in basis while keeping basic variables (including artificial) feasible. Finally, a computer implementation is accomplished to test the efficiency of our improvement comparing to the ordinary simplex algorithm on some standard test instances and randomly generated problems. The computational results show that our improved algorithms averagely spends much less executive time at each iteration than the ordinary simplex algorithm on sparse linear programming problems, and variant 2 is also competitive on dense linear programming problems. [ABSTRACT FROM AUTHOR]

In this paper, the inverse and determinant of a special kind of centrosymmetric matrices are investigated. Based on the partition property of a matrix with centrosymmetric structure and algorithms for the inverse and determinant proposed in Chen and Yu (2011), a computation algorithm for the inverse and determinant of a centrosymmetric matrix is finally developed. [ABSTRACT FROM AUTHOR]

Abstract: Using trigonometric polynomial interpolation, a fast and effective numerical algorithm for computing the inverse of a triangular Toeplitz matrix with real numbers has been recently proposed (Lin et al., 2004) [7]. The complexity of the algorithm is two fast Fourier transforms (FFTs) and one fast cosine transform (DCT) of -vectors. In this paper, we present an algorithm with two fast Fourier transforms (FFTs) of -vectors for calculating the inverse of a triangular Toeplitz matrix with real and/or complex numbers. A theoretical accuracy and error analysis is also considered. Numerical examples are given to illustrate the effectiveness of our method. [Copyright &y& Elsevier]

Abstract: In this paper, a type of smooth nonlinear optimization problems with inequality constraints is considered, and a new sequential linear equation algorithm is proposed by introducing a new constructing technique for the system of linear equations (SLE), which depends on the perturbation of the constraints’ gradients. At each iteration of the proposed algorithm, one or more SLEs need to be solved. Specially, only one SLE is required to be solved when the iterates are sufficiently close to the solution (i.e., after a finite number of iterations), which decreases the amount of computations. The search technique is a combination of the line Armijo-type and Newton step size. Under mild assumptions without the strict complementarity, it is shown that the proposed algorithm enjoys the properties of global and superlinear convergence. Finally, some preliminary numerical tests are reported, and the numerical results show that the proposed algorithm is promising. [Copyright &y& Elsevier]

Link prediction is a fundamental challenge in network science. Among various methods, similarity-based algorithms are popular for their simplicity, interpretability, high efficiency and good performance. In this paper, we show that the most elementary local similarity index Common Neighbor (CN) can be linearly decomposed by eigenvectors of the adjacency matrix of the target network, with each eigenvector's contribution being proportional to the square of the corresponding eigenvalue. As in many real networks, there is a huge gap between the largest eigenvalue and the second largest eigenvalue, the CN index is thus dominated by the leading eigenvector and much useful information contained in other eigenvectors may be overlooked. Accordingly, we propose a parameter-free algorithm that ensures the contributions of the leading eigenvector and the secondary eigenvector the same. Extensive experiments on real networks demonstrate that the prediction performance of the proposed algorithm is remarkably better than well-performed local similarity indices in the literature. A further proposed algorithm that can adjust the contribution of leading eigenvector shows the superiority over state-of-the-art algorithms with tunable parameters for its competitive accuracy and lower computational complexity. [ABSTRACT FROM AUTHOR]

• Derivation of rank-Greville algorithm, maintaining a general rank factorization. • Exploiting rank-deficiency to reach an asymptotic computational complexity of O(mr) for updating a least-squares solution when adding an observation. • Publically available implementation in Python3, using Numpy. Updating a linear least-squares solution can be critical for near real-time signal-processing applications. The Greville algorithm proposes a simple formula for updating the pseudoinverse of a matrix A ∈ R n × m with rank r. In this paper, we explicitly derive a similar formula by maintaining a general rank factorization, which we call rank-Greville. Based on this formula, we implemented a recursive least-squares algorithm exploiting the rank-deficiency of A , achieving the update of the minimum-norm least-squares solution in O (m r) operations and, therefore, solving the linear least-squares problem from scratch in O (n m r) operations. We empirically confirmed that this algorithm displays a better asymptotic time complexity than LAPACK solvers for rank-deficient matrices. The numerical stability of rank-Greville was found to be comparable to Cholesky-based solvers. Nonetheless, our implementation supports exact numerical representations of rationals, due to its remarkable algebraic simplicity. [ABSTRACT FROM AUTHOR]