Challenges in Linear and Polynomil Algebra in Symbolic Computation Algorithms
符号计算算法中线性代数和多项式代数的挑战
基本信息
- 批准号:0514585
- 负责人:
- 金额:$ 31.94万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2005
- 资助国家:美国
- 起止时间:2005-06-15 至 2009-11-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Erich Kaltofen is studying efficient algorithms for symbolic computation problems in linear and polynomial algebra that can impact applications such as geometric modeling, diophantine optimization, or cryptography. The overarching goal of the field of symbolic computation is performing mathematical computations by computer. Programs, such as Mathematica by Wolfram Research Inc. and Maple by Maplesoft, have already reached millions of users, who use them to automatically and without error perform the mechanics of mathematical manipulation. Our research affects broadly the functionality and efficiency of the underlying mathematics engine on the computer. The investigated problems provide algorithms for new tasks, and make the execution of existing procedures significantly faster, thus allowing computation with bigger models and providing mathematics servers to more users ranging from practicing scientists to high school students. Several of the algorithms have immediate application to engineering problems such as the design of Stewart-Gouch platforms. Kaltofen, under the umbrella of the LinBox group (www.linalg.org), is making the developed software freely available.The problem of decomposing a curve, surface or zero-set of polynomial equations into their components hinges on multivariate polynomial factorization. When the coefficients are imprecise due to floating point truncation or empirical measurement, the factorizations cannot be exact but must approximate the input data. We study sparse multidimensional models through employing the significant recent progress in hybrid symbolic/numeric algorithms for sparse interpolation and dense bi- and trivariate approximate polynomial factorization. Our research in exact sparse and structured linear algebra algorithms studies the control of the lengths of the intermediately computed rational numbers and the use of residue arithmetic modulo a power of 2. In the subject of polynomial factorization, we seek polynomial-time algorithms and NP-hardness proofs for problems on what we call supersparse polynomials, i.e., polynomials where the term degrees can have hundreds of digits as binary numbers. We also investigate efficient solutions for standard factorization problems, such as factorization by substituting a term for the variable. Finally, we study the problem of computing the determinant without a division and of deriving pure determinantal formulas for the resultant.
Erich Kaltofen正在研究线性和多项式代数中符号计算问题的高效算法,这些算法可能会影响几何建模、丢番图优化或密码学等应用程序。符号计算领域的首要目标是用计算机进行数学计算。像Wolfram Research Inc.的MATHEMICAL A和Maplesoft的Maple这样的程序已经接触到了数百万用户,他们使用这些程序来自动且没有错误地执行数学操作的机制。我们的研究广泛地影响了计算机上底层数学引擎的功能和效率。所调查的问题为新任务提供了算法,并使现有程序的执行速度显著加快,从而允许使用更大的模型进行计算,并为从实习科学家到高中生的更多用户提供数学服务器。其中几个算法立即应用于工程问题,如Stewart-Gouch平台的设计。在LinBox集团(www.linalg.org)旗下的Kaltofen正在使开发的软件免费提供。将曲线、曲面或多项式的零集分解成它们的分量的问题取决于多元多项式因式分解。当系数由于浮点截断或经验测量而不精确时,因式分解不是精确的,而必须近似输入数据。我们利用稀疏内插和稠密二元和三元近似多项式因式分解的符号/数值混合算法的最新进展来研究稀疏多维模型。我们对精确稀疏和结构化线性代数算法的研究研究了中间计算有理数的长度的控制和模2的剩余算术的使用。在多项式因式分解的主题中,我们寻找多项式时间算法和NP-难证明,以解决我们所称的超解析多项式的问题,即次数可以有数百位二进制数的多项式。我们还研究了标准因式分解问题的有效解,例如通过用一个术语替换变量来进行因式分解。最后,我们研究了不用除法计算行列式和导出结果的纯行列式公式的问题。
项目成果
期刊论文数量(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
Parallel Computation of Polynomial Greatest Common Divisors
多项式最大公约数的并行计算
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Erich Kaltofen - 通讯作者:
Erich Kaltofen
Factorization of Polynomials
- DOI:
10.1007/978-3-7091-7551-4_8 - 发表时间:
1983 - 期刊:
- 影响因子: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
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
AF: Small: Symbolic computation with sparsity, error checking and error correction
AF:小:具有稀疏性、错误检查和纠错的符号计算
- 批准号:
1421128 - 财政年份:2014
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
AF: Small: Efficient Exact/Certified Symbolic Computation By Hybrid Symbolic-Numeric and Parallel Methods
AF:小型:通过混合符号数字和并行方法进行高效精确/认证符号计算
- 批准号:
1115772 - 财政年份:2011
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
Model Discovery and Verification With Symbolic, Hybrid Symbolic-Numeric and Parallel Computation
使用符号、混合符号数值和并行计算进行模型发现和验证
- 批准号:
0830347 - 财政年份:2008
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
Workshop on Advanced Cyber-Enabled Discovery & Innovation (CDI) Through Symbolic and Numeric Computation
高级网络驱动发现研讨会
- 批准号:
0751501 - 财政年份:2007
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
Fast Bit Complexity in Symbolic Computation Algorithms
符号计算算法中的快速位复杂性
- 批准号:
0305314 - 财政年份:2003
- 资助金额:
$ 31.94万 - 项目类别:
Continuing Grant
ITR/ACS: Collaborative Research LinBox: A Generic Library for Seminumeric Black Box Linear Algebra
ITR/ACS:协作研究 LinBox:半数值黑盒线性代数通用库
- 批准号:
0113121 - 财政年份:2001
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
Optimization, Randomization, and Generalization in Symbolic Computation
符号计算中的优化、随机化和泛化
- 批准号:
9988177 - 财政年份:2000
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
Multi-Use "Plug-And-Play" Software Packages for Black Box and Inexact Symbolic Objects
用于黑匣子和不精确符号对象的多用途“即插即用”软件包
- 批准号:
9712267 - 财政年份:1997
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
Efficient Computer Algorithms for Symbolic Mathematics
符号数学的高效计算机算法
- 批准号:
9696203 - 财政年份:1996
- 资助金额:
$ 31.94万 - 项目类别:
Continuing Grant
相似国自然基金
Development of a Linear Stochastic Model for Wind Field Reconstruction from Limited Measurement Data
- 批准号:
- 批准年份:2020
- 资助金额:40 万元
- 项目类别:
相似海外基金
Regulation of Linear Ubiquitin Signaling in Innate Immunity
先天免疫中线性泛素信号传导的调节
- 批准号:
MR/X036944/1 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Research Grant
CAREER: Scalable algorithms for regularized and non-linear genetic models of gene expression
职业:基因表达的正则化和非线性遗传模型的可扩展算法
- 批准号:
2336469 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Continuing Grant
Statistical aspects of non-linear inverse problems
非线性反问题的统计方面
- 批准号:
EP/Y030249/1 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Research Grant
CAREER: Theoretical and Computational Advances for Enabling Robust Numerical Guarantees in Linear and Mixed Integer Programming Solvers
职业:在线性和混合整数规划求解器中实现鲁棒数值保证的理论和计算进展
- 批准号:
2340527 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Continuing Grant
CAREER: Leveraging Randomization and Structure in Computational Linear Algebra for Data Science
职业:利用计算线性代数中的随机化和结构进行数据科学
- 批准号:
2338655 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Continuing Grant
CAREER: Effective Hamiltonian Downfolding Methods for Studying Linear and Nonlinear Responses of Quantum Materials
职业:研究量子材料线性和非线性响应的有效哈密顿向下折叠方法
- 批准号:
2338704 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Continuing Grant
RII Track-4:NSF: Construction of New Additive and Semi-Implicit General Linear Methods
RII Track-4:NSF:新的加法和半隐式一般线性方法的构造
- 批准号:
2327484 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Standard Grant
DMS-EPSRC: Certifying Accuracy of Randomized Algorithms in Numerical Linear Algebra
DMS-EPSRC:验证数值线性代数中随机算法的准确性
- 批准号:
EP/Y030990/1 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Research Grant
Linear Response and Koopman Modes: Prediction and Criticality - LINK
线性响应和库普曼模式:预测和临界性 - LINK
- 批准号:
EP/Y026675/1 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Research Grant
Structural Performance Analysis of a Floating Green Energy Storage Subjected to Non-Linear Loads
非线性载荷下浮动绿色储能结构性能分析
- 批准号:
2902122 - 财政年份:2024
- 资助金额:
$ 31.94万 - 项目类别:
Studentship