【摘 要】
：
线性方程组的求解是应用数学分支数值代数的重要组成部分,被广泛应用于各个领域。特别的,对称对角占优线性方程组在计算机科学的理论和实际计算中有着广泛的应用。近年来,理论计算机方向的专家们提出了两类求解对称对角占优线性方程组的近似线性时间算法及改进。论文从优化的角度概述了由Kelner,Orecchia,Sidford和Zhu提出的一类基于环流更新的近似线性时间算法,补充了必要的证明,增加了相关的解释,
论文部分内容阅读
线性方程组的求解是应用数学分支数值代数的重要组成部分,被广泛应用于各个领域。特别的,对称对角占优线性方程组在计算机科学的理论和实际计算中有着广泛的应用。近年来,理论计算机方向的专家们提出了两类求解对称对角占优线性方程组的近似线性时间算法及改进。论文从优化的角度概述了由Kelner,Orecchia,Sidford和Zhu提出的一类基于环流更新的近似线性时间算法,补充了必要的证明,增加了相关的解释,建立了算法与优化中的随机坐标下降算法的联系。在数值方面,论文回顾了目前近似线性时间算法仅存数值实现,并结合最优化理论讨论、解释算法的数值表现。到目前为止,由对称对角占优线性方程组近似线性时间算法引出的基础图论问题、图论算法理论等方面的进步均源于近似线性时间的复杂性结论。论文对于求解对称对角占优线性方程组近似线性时间算法的理论和实现的概述为直接利用近似线性时间算法的思想来突破基础图论问题、图论算法理论及实际应用等打下了良好的基础。
其他文献
充电电池通常由正极,隔膜,负极,电解液等组成,集流体作为正负极活性材料的支撑基底,对整个电池的表现起着极为关键的作用。设计高效的集流体,使其能够在单位重量下负载更多的活性物质,从结构设计方面,提高电池的整体能量密度,具有重要的现实意义。本论文研发了一种模板电镀与刻蚀技术,用于超轻镍集流体的制备。首先通过900℃高温烧结的方法,将离散的电解铜粉烧结形成多孔基体,并以该三维连通多孔铜为模板,电镀薄层金
集邮是全世界参与人数最多、影响地区最广的收藏活动。集邮爱好者们在进行收藏活动时,通常会设立特定的主题,或是根据邮票之间的同套集或联合发行等关系进行有目的地收藏。对于集邮者们而言,将关联紧密的邮票整合在一起,再与他人分享自己的集邮进度和成果是非常有意义的过程。然而现有的邮票目录应用不展示邮票之间的复杂关系,用户难以在快节奏的现代生活中使用碎片化的时间进行关联邮票的查找。已有的互联网应用也不支持用户将
量子信息科学是一门结合量子物理、计算机科学以及信息科学的交叉性学科,包括量子通信、量子计算、量子度量和量子模拟等多个领域。光子体系是实现量子信息技术的重要物理系统之一,具有不易消相干、易于操控、制备相对简单等特点,而且光子是天然的飞行量子比特,在量子通信中发挥着不可或缺的作用。纠缠光子源是光量子信息技术应用的核心资源,在量子物理学基础研究中也发挥着重要的作用,有效产生和操控纠缠光子是国际研究的热点
近年来,随着教育和校园规划的发展,中学校园在不断扩张,中学的住校人数也与日俱增。与此同时,中学的教育理念也在不断更新。对于中学生来说,教学楼基本满足了课堂之内的教学,但对于课堂之外的教学却爱莫能助。中学宿舍楼作为学生生活时长远大于教学楼的地点,也将承担起部分课堂之外的教学重任。而公共空间作为中学宿舍楼的重要组成部分,也成为宿舍楼设计成功与否的关键点之一。在本文中,笔者结合西安创新港中学宿舍楼设计,
超构材料（Metamaterials）是具有天然材料所不具备的超常物理性质的人工复合微结构材料,在过去的几十年中,如何构建这类材料,从而实现新颖的光、声、热及力学性质,是物理学、工程学、材料科学,生命科学乃至环境科学等领域研究者共同关注的热点。近年来,作为超构材料的二维等效物,超表面（Metasurface）被广泛地用于经典波（包括电磁波和机械波等）的激发和传播的控制,即通过精巧地设计亚波长结构单
随着近些年社会经济的发展,科学技术的重要性愈发凸显,但在传统大学中分散布置的学科楼,其隔离、内向的局限性阻碍着高校学科的进一步发展。在强调创新与深化的当下,高校愈发强调学科融合和资源共享,将有交叉属性的学科联合起来形成学科链和产业链,以期各学科融合发展、相辅相成。在此背景下,相应的建筑设计模式也要发生改变,从封闭、独立走向开放、聚合,由单一性的学科楼走向集群式的学科组团。本设计为南京农业大学江北校
随着地理空间数据规模的大幅度增长与GIS应用的深入和精细化,工作研究中往往需要我们对一些海量地理空间数据进行快速处理分析,这超出了传统GIS处理模式的范畴。叠置分析作为地理空间分析中的基础算法之一,在GIS中应用十分广泛,是典型的计算密集型与数据密集型算法。为了解决叠置分析算法在面对海量复杂空间数据时处理效率低的问题,现有的研究在多核计算机以及共享内存的环境下做了很多尝试,其计算效率也得到了一定的
近几年来,堆的安全问题受到了越来越多的关注,不仅堆上的漏洞数量增多,和堆安全相关的文章也越来越多,这表明堆安全问题依旧是一个严重且实际的威胁。其中的一个原因是现有安全分配器仍然存在一些缺陷,比如不能提供充足的安全保障,或是带来不可忽略的时间开销。本文总结分析了现有安全分配器的安全措施,指出了现有工作中存在的3个缺陷:第一,现有安全分配器中对于UAF的防御措施无法有效防御UAF加堆喷射的利用方式;第
由于光子的偏振具有易操作、不易被破坏、对环境不敏感等优点,非常适合作为量子比特的载体。光子偏振纠缠已经成为量子信息领域中最常见并获得广泛应用的纠缠态之一。偏振纠缠的制备可以基于不同的材料体系,可以是基于二阶或者三阶的非线性光学效应。目前,普遍采用的一种方法是通过二阶非线性晶体中的自发参量下转换过程产生来偏振纠缠的光子对,该方案简单易行,但都是在块状晶体中或者周期极化波导中产生。本论文则致力于在单芯
建筑生成设计是计算机辅助建筑设计的有力工具,它可以通过提升工作效率、优化设计结果和提供设计可能性等多种方式来支持设计决策。但由于建筑设计问题多样化的建模方式,复杂的约束条件,以及非解析、不明确、竞争性的设计需求,使其往往难以被明确定义和直接求解。经过50多年的探索,研究者们逐步确立了交互式进化的生成设计基本工作流程,其中以进化思想为核心的随机优化方法（如遗传算法）是解决生成设计问题的首选。然而,这