Regarding an adaptive algorithm for testing multivariate linear dependence

DOI10.1016/J.LAA.2010.09.024MaRDI QIDQ616299zbMATH OpenOpenAlexFDO

Authors Ronald A. Walker

Publication date 7 January 2011

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2010.09.024

zbMATH Keywords

adaptive algorithmbinomial coefficient expansionscomplexity analysisdifferential fieldslinear dependencemarginal setYoung-like sets

Mathematics Subject Classification ID

Special families of functions of several complex variables (32A17) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms (68W40)

Review text

The author examines the complexity of his adaptive algorithm [Linear Algebra Appl. 408, 151--160 (2005; Zbl 1075.32001)] for testing linear dependence of \(N\) multivariate functions within some differential field of \(m\) variables and compare it with the complexity of generalized Wronskian techniques. It is found that the number of derivaive rows that must be calculated by this algorithm can be bounded by \(N\) plus a term that is sublinear with respect to \(N\), thus of the order \(N\) as a whole. A combinatorial argument yields a sharp bound on the size of the marginal set \({\mathcal B}_Y=\{\alpha\in{\mathbb N}^m\setminus Y\, |\, Y\cup\{a\} \text{ is Young-like}\}\) of a Young-like set \(Y\) in term of the size of \(Y\).

Recommendations

• Linear dependence of quotients of analytic functions of several variables with the least subcollection of generalized Wronskians
• Linear dependence of a function set of m variables with vanishing generalized Wronskians
• Multiplicity estimates for algebraically dependent analytic functions
• scientific article; zbMATH DE number 3345166
• A note on wronskians and linear dependence of entire functions in

Cites work

• A note on wronskians and linear dependence of entire functions in
• scientific article; zbMATH DE number 3125787 (Why is no real title available?)
• scientific article; zbMATH DE number 1222942 (Why is no real title available?)
• scientific article; zbMATH DE number 1446863 (Why is no real title available?)
• Linear dependence of a function set of m variables with vanishing generalized Wronskians
• Linear dependence of quotients of analytic functions of several variables with the least subcollection of generalized Wronskians
• Rational approximations to algebraic numbers

This page was built for publication: Regarding an adaptive algorithm for testing multivariate linear dependence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616299)