In this article, we consider the rank-structured approximation of one important type of Cauchy matrix. This approximation plays a key role in some structured matrix methods such as stable and efficient direct solvers ...
详细信息
In this article, we consider the rank-structured approximation of one important type of Cauchy matrix. This approximation plays a key role in some structured matrix methods such as stable and efficient direct solvers and other algorithms for Toeplitz matrices and certain kernel matrices. Previous rank-structured approximations (specifically hierarchically semiseparable, or HSS, approximations) for such a matrix of size n cost at least O(n) complexity. Here, we show how to construct an HSS approximation with sublinear (specifically, O(log(3)n)) complexity. The main ideas include extensive computation reuse and an analytical far-field compression strategy. Low-rank compression at each hierarchical level is restricted to just a single off-diagonal block row, and a resulting basis matrix is then reused for other off-diagonal block rows as well as off-diagonal block columns. The relationships among the off-diagonal blocks are rigorously analyzed. The far-field compression uses an analytical proxy point method where we optimize the choice of some parameters so as to obtain accurate low-rank approximations. Both the basis reuse ideas and the resulting analytical hierarchical compression scheme can be generalized to some other kernel matrices and are useful for accelerating relevant rank-structured approximations (though not subsequent operations like matrix-vector multiplications).
This paper deals with efficient numerical representation and manipulation of differential and integral operators as symbols in phase-space, i.e., functions of space x and frequency xi. The symbol smoothness conditions...
详细信息
This paper deals with efficient numerical representation and manipulation of differential and integral operators as symbols in phase-space, i.e., functions of space x and frequency xi. The symbol smoothness conditions obeyed by many operators in connection to smooth linear partial differential equations allow fast-converging, nonasymptotic expansions in adequate systems of rational Chebyshev functions or hierarchical splines to be written. The classical results of closedness of such symbol classes under multiplication, inversion, and taking the square root translate into practical iterative algorithms for realizing these operations directly in the proposed expansions. Because symbol-based numerical methods handle operators and not functions, their complexity depends on the desired resolution N very weakly, typically only through log N factors. We present three applications to computational problems related to wave propagation: (1) preconditioning the Helmholtz equation, (2) decomposing wave fields into one-way components, and (3) depth extrapolation in reflection seismology. The software is made available in the software sections of ***/similar to laurent and ***/users/lexing.
This paper explores the use of a double-base number system (DBNS) in constant integer multiplication. The DBNS recoding technique represents constants in a multiple-radix way in the hopes of minimizing computation dur...
详细信息
ISBN:
(纸本)0819463922
This paper explores the use of a double-base number system (DBNS) in constant integer multiplication. The DBNS recoding technique represents constants in a multiple-radix way in the hopes of minimizing computation during constant multiplication. The paper presents a proof to show that multiple-radix representation diminishes the number of additions in a sublinear way. We prove Lefevre's conjecture that the multiplication by an integer constant is achievable in sublinear time. The proof is based on some interesting properties of the double-base number system. The paper provides numerical data showcasing some of the most recent results.
In this paper we address the problem of quick detection of high-degree entities in large online social networks. Practical importance of this problem is attested by a large number of companies that continuously collec...
详细信息
ISBN:
(纸本)9781479943036
In this paper we address the problem of quick detection of high-degree entities in large online social networks. Practical importance of this problem is attested by a large number of companies that continuously collect and update statistics about popular entities, usually using the degree of an entity as an approximation of its popularity. We suggest a simple, efficient, and easy to implement two-stage randomized algorithm that provides highly accurate solutions to this problem. For instance, our algorithm needs only one thousand API requests in order to find the top-00 most followed users, with more than 90% precision, in the online social network Twitter with approximately a billion of registered users. Our algorithm significantly outperforms existing methods and serves many different purposes such as finding the most popular users or the most popular interest groups in social networks. An important contribution of this work is the analysis of the proposed algorithm using Extreme Value Theory - a branch of probability that studies extreme events and properties of largest order statistics in random samples. Using this theory we derive an accurate prediction for the algorithm's performance and show that the number of API requests for finding the top-k most popular entities is sublinear in the number of entities. Moreover, we formally show that the high variability of the entities, expressed through heavy-tailed distributions, is the reason for the algorithm's efficiency. We quantify this phenomenon in a rigorous mathematical way.
Scalability to large numbers of classes is an important challenge for multi-class classification. It can often be computationally infeasible at test phase when class prediction is performed by using every possible cla...
详细信息
ISBN:
(纸本)9781479900152
Scalability to large numbers of classes is an important challenge for multi-class classification. It can often be computationally infeasible at test phase when class prediction is performed by using every possible classifier trained for each individual class. This paper proposes an attribute-based learning method to overcome this limitation. First is to define attributes and their associations with object classes automatically and simultaneously. Such associations are learned based on greedy strategy under certain conditions. Second is to learn a classifier for each attribute instead of each class. Then, these trained classifiers are used to predict classes based on their attribute representations. The proposed method also allows trade-off between test-time complexity (which grows linearly with the number of attributes) and accuracy. Experiments based on Animals-with-Attributes and ILSVRC2010 datasets have shown that the performance of our method is promising when compared with the state-of-the-art.
This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating...
详细信息
This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.
暂无评论