BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Victor Y. Pan

Victor Y. Pan contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.NANumerical AnalysisSymbolic ComputationData Structures and Algorithmsmath.PR

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
21works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

21 published item(s)

preprint2022arXiv

Accelerated Subdivision for Clustering Roots of Polynomials given by Evaluation Oracles

In our quest for the design, the analysis and the implementation of a subdivision algorithm for finding the complex roots of univariate polynomials given by oracles for their evaluation, we present sub-algorithms allowing substantial acceleration of subdivision for complex roots clustering for such polynomials. We rely on Cauchy sums which approximate power sums of the roots in a fixed complex disc and can be computed in a small number of evaluations --polylogarithmic in the degree. We describe root exclusion, root counting, root radius approximation and a procedure for contracting a disc towards the cluster of root it contains, called $\varepsilon$-compression. To demonstrate the efficiency of our algorithms, we combine them in a prototype root clustering algorithm. For computing clusters of roots of polynomials that can be evaluated fast, our implementation competes advantageously with user's choice for root finding, MPsolve.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

New Progress in Classic Area: Polynomial Root-squaring and Root-finding

The DLG root-squaring iterations, due to Dandelin 1826 and rediscovered by Lobachevsky 1834 and Graeffe 1837, have been the main approach to root-finding for a univariate polynomial p(x) in the 19th century and beyond, but not so nowadays because these iterations are prone to severe numerical stability problems. Trying to avoid these problems we have found simple but novel reduction of the iterations applied for Newton's inverse ratio -p'(x)/p(x) to approximation of the power sums of the zeros of p(x) and its reverse polynomial. The resulting polynomial root-finders can be devised and performed independently of DLG iterations, based on Newton's identities or Cauchy integrals. In the former case the computation involve a set of leading or tailing coefficients of an input polynomial. In the latter case we must scale the variable and increase the arithmetic computational cost to ensure numerical stability. Nevertheless the cost is still manageable, at least for fast root-refinement, and the algorithms can be applied to a black box polynomial p(x)--given by a black box for the evaluation of the ratio p'(x)/p(x) rather than by its coefficients. This enables important computational benefits, including efficient recursive as well as concurrent approximation of a set of zeros of p(x) or even all of its zeros, acceleration where an input polynomial can be evaluated fast, and extension to approximation of the eigenvalues of a matrix or a polynomial matrix, being efficient if the matrix can be inverted fast, e.g., is data sparse. We also recall our recent fast algorithms for approximation of the root radii, that is, the distances to the roots from the origin or any complex value to the zeros of p(x), and apply it for fast black box initialization of polynomial root-finding by means of functional iterations, e.g., Newton's, Ehrlich's, and Weierstrass's.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Low-rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions

Low-rank approximation of a matrix by means of random sampling has been consistently efficient in its empirical studies by many scientists who applied it with various sparse and structured multipliers, but adequate formal support for this empirical phenomenon has been missing so far. Our novel insight into the subject leads to such an elusive formal support and promises significant acceleration of the known algorithms for some fundamental problems of matrix computations and data mining and analysis. Our formal results and our numerical tests are in good accordance with each other. We also outline extensions of low-rank approximation algorithms and of our progress to the Least Squares Regression, the Fast Multipole Method, and the Conjugate Gradient algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New Studies of Randomized Augmentation and Additive Preprocessing

1. A standard Gaussian random matrix has full rank with probability 1 and is well-conditioned with a probability quite close to 1 and converging to 1 fast as the matrix deviates from square shape and becomes more rectangular. 2. If we append sufficiently many standard Gaussian random rows or columns to any normalized matrix A, then the augmented matrix has full rank with probability 1 and is well-conditioned with a probability close to 1, even if the matrix A is rank deficient or ill-conditioned. 3. We specify and prove these properties of augmentation and extend them to additive preprocessing, that is, to adding a product of two rectangular Gaussian matrices. 4. By applying our randomization techniques to a matrix that has numerical rank r, we accelerate the known algorithms for the approximation of its leading and trailing singular spaces associated with its r largest and with all its remaining singular values, respectively. 5. Our algorithms use much fewer random parameters and run much faster when various random sparse and structured preprocessors replace Gaussian. Empirically the outputs of the resulting algorithms is as accurate as the outputs under Gaussian preprocessing. 6. Our novel duality techniques provides formal support, so far missing, for these empirical observations and opens door to derandomization of our preprocessing and to further acceleration and simplification of our algorithms by using more efficient sparse and structured preprocessors. 7. Our techniques and our progress can be applied to various other fundamental matrix computations such as the celebrated low-rank approximation of a matrix by means of random sampling.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

How Bad Are Vandermonde Matrices?

The work on the estimation of the condition numbers of Vandermonde matrices, motivated by applications to interpolation and quadrature, can be traced back at least to the 1970s. Empirical study has shown consistently that Vandermonde matrices tend to be badly ill-conditioned, with a narrow class of notable exceptions, such as the matrices of the discrete Fourier transform (hereafter referred to as DFT). So far formal support for this empirical observation, however, has been limited to the matrices defined by the real set of knots. We prove that, more generally, any Vandermonde matrix of a large size is badly ill-conditioned unless its knots are more or less equally spaced on or about the circle $C(0,1)=\{x:\,|x|=1\}$. The matrices of DFT are perfectly conditioned, being defined by a cyclic sequence of knots, equally spaced on that circle, but we prove that even a slight modification of the knots into the so called quasi-cyclic sequence on this circle defines badly ill-conditioned Vandermonde matrices. Likewise we prove that the half-size leading block of a large DFT matrix is badly ill-conditioned. (This result was motivated by an application to pre-conditioning of an input matrix for Gaussian elimination with no pivoting.) Our analysis involves the Ekkart--Young theorem, the Vandermonde-to-Cauchy transformation of matrix structure, our new inversion formula for a Cauchy matrix, and low-rank approximation of its large submatrices.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Matrix Multiplication, Trilinear Decompositions, APA Algorithms, and Summation

Matrix multiplication (hereafter we use the acronym MM) is among the most fundamental operations of modern computations. The efficiency of its performance depends on various factors, in particular vectorization, data movement and arithmetic complexity of the computations, but here we focus just on the study of the arithmetic cost and the impact of this study on other areas of modern computing. In the early 1970s it was expected that the straightforward cubic time algorithm for MM will soon be accelerated to enable MM in nearly quadratic arithmetic time, with some far fetched implications. While pursuing this goal the mainstream research had its focus on the decrease of the classical exponent 3 of the complexity of MM towards its lower bound 2, disregarding the growth of the input size required to support this decrease. Eventually, surprising combinations of novel ideas and sophisticated techniques enabled the decrease of the exponent to its benchmark value of about 2.38, but the supporting MM algorithms improved the straightforward one only for the inputs of immense sizes. Meanwhile, the communication complexity, rather than the arithmetic complexity, has become the bottleneck of computations in linear algebra. This development may seem to undermine the value of the past and future research aimed at the decrease of the arithmetic cost of MM, but we feel that the study should be reassessed rather than closed and forgotten. We review the old and new work in this area in the present day context, recall some major techniques introduced in the study of MM, discuss their impact on the modern theory and practice of computations for MM and beyond MM, and link one of these techniques to some simple algorithms for inner product and summation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Polynomial Root Isolation by Means of Root Radii Approximation

Univariate polynomial root-finding is a classical subject, still important for modern computing. Frequently one seeks just the real roots of a real coefficient polynomial. They can be approximated at a low computational cost if the polynomial has no nonreal roots, but for high degree polynomials, nonreal roots are typically much more numerous than the real ones. The challenge is known for long time, and the subject has been intensively studied. The Boolean cost bounds for the refinement of the simple and isolated real roots have been decreased to nearly optimal, but the success has been more limited at the stage of the isolation of real roots. We obtain substantial progress by applying the algorithm of of 1982 by Schoenhage for the approximation of the root radii, that is, the distances of the roots to the origin. Namely we isolate the simple and well-conditioned real roots of a polynomial at the Boolean cost dominated by the nearly optimal bounds for the refinement of such roots. We also extend our algorithm to the isolation of complex, possibly multiple, roots and root clusters staying within the same (nearly optimal) asymptotic Boolean cost bound. Our numerical tests with benchmark polynomials performed with the IEEE standard double precision show that our nearly optimal real root-finder is practically promising. Our techniques are simple, and their power and application range may increase in combination with the known efficient methods.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Accelerated Approximation of the Complex Roots of a Univariate Polynomial (Extended Abstract)

Highly efficient and even nearly optimal algorithms have been developed for the classical problem of univariate polynomial root-finding (see, e.g., \cite{P95}, \cite{P02}, \cite{MNP13}, and the bibliography therein), but this is still an area of active research. By combining some powerful techniques developed in this area we devise new nearly optimal algorithms, whose substantial merit is their simplicity, important for the implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Better Late Than Never: Filling a Void in the History of Fast Matrix Multiplication and Tensor Decompositions

Multilinear and tensor decompositions are a popular tool in linear and multilinear algebra and have a wide range of important applications to modern computing. Our paper of 1972 presented the first nontrivial application of such decompositions to fundamental matrix computations and was also a landmark in the history of the acceleration of matrix multiplication. Published in 1972 in Russian, it has never been translated into English. It has been very rarely cited in the Western literature on matrix multiplication and never in the works on multilinear and tensor decompositions. This motivates us to present its translation into English, together with our brief comments on its impact on the two fields.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Nearly Optimal Computations with Structured Matrices

We estimate the Boolean complexity of multiplication of structured matrices by a vector and the solution of nonsingular linear systems of equations with these matrices. We study four basic most popular classes, that is, Toeplitz, Hankel, Cauchy and Van-der-monde matrices, for which the cited computational problems are equivalent to the task of polynomial multiplication and division and polynomial and rational multipoint evaluation and interpolation. The Boolean cost estimates for the latter problems have been obtained by Kirrinnis in \cite{kirrinnis-joc-1998}, except for rational interpolation, which we supply now. All known Boolean cost estimates for these problems rely on using Kronecker product. This implies the $d$-fold precision increase for the $d$-th degree output, but we avoid such an increase by relying on distinct techniques based on employing FFT. Furthermore we simplify the analysis and make it more transparent by combining the representation of our tasks and algorithms in terms of both structured matrices and polynomials and rational functions. This also enables further extensions of our estimates to cover Trummer's important problem and computations with the popular classes of structured matrices that generalize the four cited basic matrix classes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Novel Approach to Real Polynomial Root-finding and Matrix Eigen-solving

Univariate polynomial root-finding is both classical and important for modern computing. Frequently one seeks just the real roots of a polynomial with real coefficients. They can be approximated at a low computational cost if the polynomial has no nonreal roots, but typically nonreal roots are much more numerous than the real ones. We dramatically accelerate the known algorithms in this case by exploiting the correlation between the computations with matrices and polynomials, extending the techniques of the matrix sign iteration, and exploiting the structure of the companion matrix of the input polynomial. We extend some of the proposed techniques to the approximation of the real eigenvalues of a real nonsymmetric matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Random Multipliers Numerically Stabilize Gaussian and Block Gaussian Elimination: Proofs and an Extension to Low-rank Approximation

We prove that standard Gaussian random multipliers are expected to numerically stabilize both Gaussian elimination with no pivoting and block Gaussian elimination. Moreover we prove that such a multiplier (even without the customary oversampling) is expected to support low-rank approximation of a matrix. Our test results are in good accordance with this analysis. Empirically random circulant or Toeplitz multipliers are as efficient as Gaussian ones, but their formal support is more problematic.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Chapter 10: Algebraic Algorithms

Our Chapter in the upcoming Volume I: Computer Science and Software Engineering of Computing Handbook (Third edition), Allen Tucker, Teo Gonzales and Jorge L. Diaz-Herrera, editors, covers Algebraic Algorithms, both symbolic and numerical, for matrix computations and root-finding for polynomials and systems of polynomials equations. We cover part of these large subjects and include basic bibliography for further study. To meet space limitation we cite books, surveys, and comprehensive articles with pointers to further references, rather than including all the original technical papers.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Estimating the Norms of Random Circulant and Toeplitz Matrices and Their Inverses

We estimate the norms of standard Gaussian random Toeplitz and circulant matrices and their inverses, mostly by means of combining some basic techniques of linear algebra. In the case of circulant matrices we obtain sharp probabilistic estimates, which show that these matrices are expected to be very well conditioned. Our probabilistic estimates for the norms of standard Gaussian random Toeplitz matrices are within a factor of 1.4143 from those in the circulant case. We also achieve partial progress in estimating the norms of Toeplitz inverses. Namely we yield reasonable probabilistic upper estimates for these norms assuming certain bounds on the absolute values of two corner entries of the inverse. Empirically we observe that the condition numbers of random Toeplitz and general matrices tend to be of the same order. As the matrix size grows, these numbers grow equally slowly, although faster than for random circulant matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Transformations of Matrix Structures Work Again

In 1989 we proposed to employ Vandermonde and Hankel multipliers to transform into each other the matrix structures of Toeplitz, Hankel, Vandermonde and Cauchy types as a means of extending any successful algorithm for the inversion of matrices having one of these structures to inverting the matrices with the structures of the three other types. Surprising power of this approach has been demonstrated in a number of works, which culminated in ingeneous numerically stable algorithms that approximated the solution of a nonsingular Toeplitz linear system in nearly linear (versus previuosly cubic) arithmetic time. We first revisit this powerful method, covering it comprehensively, and then specialize it to yield a similar acceleration of the known algorithms for computations with matrices having structures of Vandermonde or Cauchy types. In particular we arrive at numerically stable approximate multipoint polynomial evaluation and interpolation in nearly linear arithmetic time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Transformations of Matrix Structures Work Again II

Matrices with the structures of Toeplitz, Hankel, Vandermonde and Cauchy types are omnipresent in modern computation. The four classes have distinct features, but in 1990 we showed that Vandermonde and Hankel multipliers transform all these structures into each other and proposed to employ this property to extend any successful algorithm that inverts matrices of one of these classes to inverting matrices of the three other classes. The power of this approach was widely recognized later, when novel numerically stable algorithms solved nonsingular Toeplitz linear systems of equations at first in quadratic and then in nearly linear (versus classical cubic) arithmetic time by means of transforming Toeplitz into Cauchy matrix structures and then linking it to the Hierarchical Semiseparable matrix structure, a specialization of matrix representations employed by the Fast Multipole Method. We first cover the method of structure transformation comprehensively, then analyze the latter algorithms for Toeplitz linear systems and extend them to approximate the products of Vandermonde and Cauchy matrices by a vector and the solutions of Vandermonde and Cauchy linear systems of equations where they are nonsingular and well conditioned. We decrease the arithmetic cost of the known algorithms from quadratic to nearly linear, and similarly for the computations with the matrices of a more general class having structures of Vandermonde and Cauchy types and for polynomial and rational evaluation and interpolation. We also accelerate a little further the known numerical approximation algorithms for a nonsingular Toeplitz or Toeplitz-like linear system by employing distinct transformations of matrix structures, and we briefly discuss some natural research challenges, particularly some promising applications of our techniques to high precision computations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Condition Numbers of Random Toeplitz and Circulant Matrices

Estimating the condition numbers of random structured matrices is a well known challenge, linked to the design of efficient randomized matrix algorithms. We deduce such estimates for Gaussian random Toeplitz and circulant matrices. The former estimates can be surprising because the condition numbers grow exponentially in n as n grows to infinity for some large and important classes of n-by-n Toeplitz matrices, whereas we prove the opposit for Gaussian random Toeplitz matrices. Our formal estimates are in good accordance with our numerical tests, except that circulant matrices tend to be even better conditioned according to the tests than according to our formal study.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

More on the Power of Randomized Matrix Computations

A random matrix is likely to be well conditioned, and motivated by this well known property we employ random matrix multipliers to advance some fundamental matrix computations. This includes numerical stabilization of Gaussian elimination with no pivoting as well as block Gaussian elimination, approximation of the leading and trailing singular spaces of an ill conditioned matrix, associated with its largest and smallest singular values, respectively, and approximation of this matrix by low-rank matrices, with further extensions to computing numerical ranks and the approximation of tensor decomposition. We formally support the efficiency of the proposed techniques where we employ Gaussian random multipliers, but our extensive tests have consistently produced the same outcome where instead we used sparse and structured random multipliers, defined by much fewer random parameters compared to the number of their entries.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Randomized Matrix Computations

Random matrices tend to be well conditioned, and we employ this well known property to advance matrix computations. We prove that our algorithms employing Gaussian random matrices are efficient, but in our tests the algorithms have consistently remained as powerful where we used sparse and structured random matrices, defined by much fewer random parameters. We numerically stabilize Gaussian elimination with no pivoting as well as block Gaussian elimination, precondition an ill conditioned linear system of equations, compute numerical rank of a matrix without orthogonalization and pivoting, approximate the singular spaces of an ill conditioned matrix associated with its largest and smallest singular values, and approximate this matrix with low-rank matrices, with applications to its 2-by-2 block triangulation and to tensor decomposition. Some of our results and techniques can be of independent interest, e.g., our estimates for the condition numbers of random Toeplitz and circulant matrices and our variations of the Sherman--Morrison--Woodbury formula.

0 citations0 reviewsNo code linkedOpen access