Optimization, Randomization, and Generalization in Symbolic Computation
符号计算中的优化、随机化和泛化
基本信息
- 批准号:9988177
- 负责人:
- 金额:$ 26.22万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2000
- 资助国家:美国
- 起止时间:2000-06-01 至 2003-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Erich Kaltofen proposes to study mathematical optimization techniques on problem formulations that are imprecise due to numerical data; randomization techniques that are the power tools in the design of fast algorithms with exact arithmetic on black box matrices; and generalization of the computer programs that implement these algorithms to multiple domains with methodologies such as generic, reusable programming and interface protocols. A difficulty in the symbolic/numeric area is that inputs with imprecise coefficients as a result of a physical measurement or a numerical computation can lack a known property that is of interest. For example, instead of a double real root, a polynomial has two conjugate complex roots that are very close together. The optimization problem is to compute efficiently the nearest input that has the desired singularity.Our focus will be on the nearest pair of polynomials with a common root under coefficient-wise change (infinity norm), the nearest singular Toeplitz matrix, and the nearest bi-variate complex polynomial that factors over the complex numbers, the latter two under any reasonable norm. A black box matrix is stored as a function that performs the matrix-times vector product. Efficient algorithms for performing linear algebra computations with exact field arithmetic, such as solving a linearsystem with a black box coefficient matrix, are based on the Lanczos/Wiedemann approach.Randomization techniques, for instance, matrix pre-conditioning and Krylov sub-spacing with random projections, avoid self-orthogonality when the coefficients are from a finite field and general algorithmicbreak-down due to certain invariant factors of the matrix. We propose to investigate how the different linear algebra problems are interelated, for example if the computation of a solution of an inhomogeneous black box linear system can be efficiently reduced to the computation of a column dependency of a black box matrix. Generic programming is a software design technique that generalizes a program so that it can be used with more than one underlying domain. The proposed implementation of our black box algorithms notonly permits the plug-in of a black box matrix over a native coefficient field, but the code also imports internally needed operations like polynomial and vector operations from expertly fine-tuned existing packages across generic interfaces. Our library's application program interface provides a serialization mechanism for black box objects that is compliant with the MathML/OpenMath philosophy and that allowsInternet communication. Finally, we propose research on two classical problems. First, the polynomial-time computation of dense, low-degree factors of high-degree sparse multi-variate polynomials with rational coefficients, which would generalize a recent related result by Hendrik W. Lenstra, Jr. Second, a time- and space-efficient realization of the transposition principle for transforming a matrix-times-vector function to the transpose vector-times-matrix operation.
埃里希Kaltofen建议研究数学优化技术的问题配方是不精确的,由于数值数据;随机化技术,这是在设计快速算法与黑盒矩阵的精确运算的动力工具;和一般化的计算机程序,实现这些算法到多个领域的方法,如通用的,可重用的编程和接口协议。 符号/数字领域的一个困难是,作为物理测量或数值计算的结果,具有不精确系数的输入可能缺乏感兴趣的已知属性。例如,多项式不是双真实的根,而是有两个非常接近的共轭复根。 最优化问题是有效地计算具有期望奇异性的最近输入。我们的重点将是在系数变化(无穷范数)下具有公共根的最近多项式对,最近的奇异Toeplitz矩阵,以及最近的在复数上因子化的二元复多项式,后两者在任何合理的范数下。 黑盒矩阵被存储为执行矩阵乘以向量积的函数。 用精确域算法进行线性代数计算的有效算法,如求解具有黑盒系数矩阵的线性方程组,是基于Lanczos/Wiedemann方法的,随机化技术,如矩阵预处理和Krylov子间隔随机投影,避免了系数来自有限域时的自正交性和由于矩阵的某些不变因子而导致的一般算法故障。我们建议调查如何不同的线性代数问题是相互关联的,例如,如果计算的解决方案的非齐次黑盒线性系统可以有效地减少到计算的黑盒矩阵的列依赖性。 泛型编程是一种软件设计技术,它使程序通用化,以便它可以与多个底层域一起使用。 我们的黑盒算法的拟议实现不仅允许在本地系数字段上插入黑盒矩阵,而且代码还从跨通用接口的专业微调的现有包中导入内部需要的操作,例如多项式和向量操作。我们的库的应用程序接口为黑盒对象提供了一种序列化机制,该机制符合MathML/OpenMath哲学,并允许Internet通信。 最后,我们提出了两个经典问题的研究。首先,研究了有理系数高次稀疏多元多项式的稠密低次因子的多项式时间计算,推广了Hendrik W.小伦斯特拉第二,将矩阵乘向量函数变换为转置向量乘矩阵运算的转置原理的时间和空间有效实现。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Erich Kaltofen其他文献
Deterministic distinct-degree factorization of polynomials over finite fields
有限域上多项式的确定性异次因式分解
- DOI:
- 发表时间:
2004 - 期刊:
- 影响因子:0.7
- 作者:
Shuhong Gao;Erich Kaltofen;Alan G. B. Lauder - 通讯作者:
Alan G. B. Lauder
What is Hybrid Symbolic-Numeric Computation?
- DOI:
10.1109/synasc.2011.65 - 发表时间:
2011-09 - 期刊:
- 影响因子:0
- 作者:
Erich Kaltofen - 通讯作者:
Erich Kaltofen
Factorization of Polynomials
- DOI:
10.1007/978-3-7091-7551-4_8 - 发表时间:
1983 - 期刊:
- 影响因子:0
- 作者:
Erich Kaltofen - 通讯作者:
Erich Kaltofen
Parallel Computation of Polynomial Greatest Common Divisors
多项式最大公约数的并行计算
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Erich Kaltofen - 通讯作者:
Erich Kaltofen
Erich Kaltofen的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Erich Kaltofen', 18)}}的其他基金
AF: Small: Symbolic Computation with Certificates, Sparsity and Error Correction
AF:小:带有证书、稀疏性和纠错的符号计算
- 批准号:
1717100 - 财政年份:2017
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
AF: Small: Symbolic computation with sparsity, error checking and error correction
AF:小:具有稀疏性、错误检查和纠错的符号计算
- 批准号:
1421128 - 财政年份:2014
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
AF: Small: Efficient Exact/Certified Symbolic Computation By Hybrid Symbolic-Numeric and Parallel Methods
AF:小型:通过混合符号数字和并行方法进行高效精确/认证符号计算
- 批准号:
1115772 - 财政年份:2011
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
Model Discovery and Verification With Symbolic, Hybrid Symbolic-Numeric and Parallel Computation
使用符号、混合符号数值和并行计算进行模型发现和验证
- 批准号:
0830347 - 财政年份:2008
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
Workshop on Advanced Cyber-Enabled Discovery & Innovation (CDI) Through Symbolic and Numeric Computation
高级网络驱动发现研讨会
- 批准号:
0751501 - 财政年份:2007
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
Challenges in Linear and Polynomil Algebra in Symbolic Computation Algorithms
符号计算算法中线性代数和多项式代数的挑战
- 批准号:
0514585 - 财政年份:2005
- 资助金额:
$ 26.22万 - 项目类别:
Continuing Grant
Fast Bit Complexity in Symbolic Computation Algorithms
符号计算算法中的快速位复杂性
- 批准号:
0305314 - 财政年份:2003
- 资助金额:
$ 26.22万 - 项目类别:
Continuing Grant
ITR/ACS: Collaborative Research LinBox: A Generic Library for Seminumeric Black Box Linear Algebra
ITR/ACS:协作研究 LinBox:半数值黑盒线性代数通用库
- 批准号:
0113121 - 财政年份:2001
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
Multi-Use "Plug-And-Play" Software Packages for Black Box and Inexact Symbolic Objects
用于黑匣子和不精确符号对象的多用途“即插即用”软件包
- 批准号:
9712267 - 财政年份:1997
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
Efficient Computer Algorithms for Symbolic Mathematics
符号数学的高效计算机算法
- 批准号:
9696203 - 财政年份:1996
- 资助金额:
$ 26.22万 - 项目类别:
Continuing Grant
相似海外基金
CAREER: Leveraging Randomization and Structure in Computational Linear Algebra for Data Science
职业:利用计算线性代数中的随机化和结构进行数据科学
- 批准号:
2338655 - 财政年份:2024
- 资助金额:
$ 26.22万 - 项目类别:
Continuing Grant
The Ethics of Randomization in Social Science Experiments
社会科学实验中随机化的伦理
- 批准号:
2316155 - 财政年份:2024
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
CAREER: New Challenges in Statistical Genetics: Mendelian Randomization, Integrated Omics and General Methodology
职业:统计遗传学的新挑战:孟德尔随机化、综合组学和通用方法论
- 批准号:
2238656 - 财政年份:2023
- 资助金额:
$ 26.22万 - 项目类别:
Continuing Grant
Plasma proteomic biomarkers of aortic stenosis: A Mendelian randomization study.
主动脉瓣狭窄的血浆蛋白质组生物标志物:孟德尔随机研究。
- 批准号:
495590 - 财政年份:2023
- 资助金额:
$ 26.22万 - 项目类别:
CAREER: Advances in Randomization Inference for Causal Effects: Heterogeneity, Sensitivity, and Complexity
职业:因果效应随机推理的进展:异质性、敏感性和复杂性
- 批准号:
2238128 - 财政年份:2023
- 资助金额:
$ 26.22万 - 项目类别:
Continuing Grant
CAREER: Advances in Randomization Inference for Causal Effects: Heterogeneity, Sensitivity, and Complexity
职业:因果效应随机推理的进展:异质性、敏感性和复杂性
- 批准号:
2400961 - 财政年份:2023
- 资助金额:
$ 26.22万 - 项目类别:
Continuing Grant
Mendelian randomization for modern data: Integrating data resources to improve accuracy of causal estimates.
现代数据的孟德尔随机化:整合数据资源以提高因果估计的准确性。
- 批准号:
10716241 - 财政年份:2023
- 资助金额:
$ 26.22万 - 项目类别:
A comprehensive Mendelian Randomization on the causal pathway from psychological traits to all-cause mortality
从心理特征到全因死亡率的因果路径的全面孟德尔随机化
- 批准号:
22H03354 - 财政年份:2022
- 资助金额:
$ 26.22万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Collaborative Research: Randomization Based Machine Learning Methods in a Bayesian Model Setting for Data From a Complex Survey or Census
协作研究:针对复杂调查或人口普查数据的贝叶斯模型设置中基于随机化的机器学习方法
- 批准号:
2215169 - 财政年份:2022
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant
Collaborative Research: Randomization Based Machine Learning Methods in a Bayesian Model Setting for Data From a Complex Survey or Census
协作研究:针对复杂调查或人口普查数据的贝叶斯模型设置中基于随机化的机器学习方法
- 批准号:
2215168 - 财政年份:2022
- 资助金额:
$ 26.22万 - 项目类别:
Standard Grant














{{item.name}}会员




