Source author record

Victor Pan

Victor Pan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Symbolic Computation math.NA Numerical Analysis

Catalog footprint

What is connected

3works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Fast Derandomized Low-rank Approximation and Extensions

Low-rank approximation of a matrix by means of structured random sampling has been consistently efficient in its extensive empirical studies around the globe, but adequate formal support for this empirical phenomenon has been missing so far. Based on our novel insight into the subject, we provide such an elusive formal support and derandomize and simplify the known numerical algorithms for low-rank approximation and related computations. Our techniques can be applied to some other areas of fundamental matrix computations, in particular to the Least Squares Regression, Gaussian elimination with no pivoting and block Gaussian elimination. Our formal results and our numerical tests are in good accordance with each other.

preprint2016arXiv

Fast Matrix Multiplication and Symbolic Computation

The complexity of matrix multiplication (hereafter MM) has been intensively studied since 1969, when Strassen surprisingly decreased the exponent 3 in the cubic cost of the straightforward classical MM to log 2 (7) $\approx$ 2.8074. Applications to some fundamental problems of Linear Algebra and Computer Science have been immediately recognized, but the researchers in Computer Algebra keep discovering more and more applications even today, with no sign of slowdown. We survey the unfinished history of decreasing the exponent towards its information lower bound 2, recall some important techniques discovered in this process and linked to other fields of computing, reveal sample surprising applications to fast computation of the inner products of two vectors and summation of integers, and discuss the curse of recursion, which separates the progress in fast MM into its most acclaimed and purely theoretical part and into valuable acceleration of MM of feasible sizes. Then, in the second part of our paper, we cover fast MM in realistic symbolic computations and discuss applications and implementation of fast exact matrix multiplication. We first review how most of exact linear algebra can be reduced to matrix multiplication over small finite fields. Then we highlight the differences in the design of approximate and exact implementations of fast MM, taking into account nowadays processor and memory hierarchies. In the concluding section we comment on current perspectives of the study of fast MM.

preprint2014arXiv

Global Newton Iteration over Archimedean and non-Archimedean Fields

In this paper, we study iterative methods on the coefficients of the rational univariate representation (RUR) of a given algebraic set, called global Newton iteration. We compare two natural approaches to define locally quadratically convergent iterations: the first one involves Newton iteration applied to the approximate roots individually and then interpolation to find the RUR of these approximate roots; the second one considers the coefficients in the exact RUR as zeroes of a high dimensional map defined by polynomial reduction, and applies Newton iteration on this map. We prove that over fields with a p-adic valuation these two approaches give the same iteration function, but over fields equipped with the usual Archimedean absolute value, they are not equivalent. In the latter case, we give explicitly the iteration function for both approaches. Finally, we analyze the parallel complexity of the different versions of the global Newton iteration, compare them, and demonstrate that they can be efficiently computed. The motivation for this study comes from the certification of approximate roots of overdetermined and singular polynomial systems via the recovery of an exact RUR from approximate numerical data.