1. 因子分解1.1 唯一分解环环的直和分解将大环分解为小环，使得结构更加简单。从整数的算术基本定理得到启发，我们还可以从乘法分解的角度来研究环。要使这个定向研究得到有用的结论，还需对环作一些限制。既然我们关注是因子，乘法顺序就显得多余且碍事，所以要求环是可交换的。另外零因子的讨论也是没有意义的，故规定所有非零元素都是正则元。故我们只需讨论整环中元素的乘法分解，为简化描述，以下将忽略对零元素的讨论。和初等数论中一样，若\(a=bc\)，称\(b\)整除\(a\)，或\(b\)是\(a\)的因子，记作\(b\mid a\)，否则记作\(b\not\mid a\)。关于整除的常规讨论都比较简单，这里不再赘述。我们把注意力放在分解的多种可能性上，最后试图得到类似算术基本定理的结论。在分解的过程中，可逆元总是可以随处出现或消除，它就像整数环中的\(\pm 1\)，并不影响分解的本质。这就是为什么可逆元\(\varepsilon\)也叫单位，如果\(a=b\varepsilon\)，我们\(a,b\)称是相伴的，相伴元在分解中可以可作是等价的。既然要考虑可逆元，就必须要求乘法存在单位元，故以下讨论仅针对有单位元的整环。对任意元素\(a\)，它的所有相伴元和单位都是\(a\)的平凡因子，其它的则是真因子。有真因子的元素叫可约元，否则叫不可约元，显然整数环的不可约元就是素数。有了因子和不可约元的 ...继续阅读 (17)

OpenCASCADE Interpolation - Lagrangeeryar@163.comAbstract.Power basis polynomial is the most simple polynomial function. It also be called power series. OpenCASCADE provides basic computation functions for polynomial functions, such as evaluate the result for a given polynomial, Lagrange interpolation, Hermite interpolation, .etc. The package named PLib, means Polynomial functions Library. The paper focus on the Lagrange interpolation usage of PLib.Key Words.OpenCASCADE, PLib, Interpolation, Lagrange, 插值 1.Introduction无 穷级数是高等数学的一个重要组成部分，它是表示函数、研究函数性质及进行数值计算的一种工具。由高等数学中的无穷级数的概念可知，函数项级数中简单 ...继续阅读 (23)

OpenCASCADE Interpolation - Lagrangeeryar@163.comAbstract.Power basis polynomial is the most simple polynomial function. It also be called power series. OpenCASCADE provides basic computation functions for polynomial functions, such as evaluate the result for a given polynomial, Lagrange interpolation, Hermite interpolation, .etc. The package named PLib, means Polynomial functions Library. The paper focus on the Lagrange interpolation usage of PLib.Key Words.OpenCASCADE, PLib, Interpolation, Lagrange, 插值1.Introduction无穷级数是高等数学的一个重要组成部分，它是表示函数、研究函数性质及进行数值计算的一种工具。由高等数学中的无穷级数的概念可知，函数项级数中简单而常见的一类级 ...继续阅读 (82)

时间复杂度计算实例表示时间复杂度的阶有：O(1) ：常量时间阶 O (n)：线性时间阶O(㏒n) ：对数时间阶 O(n㏒n) ：线性对数时间阶O (nk)： k≥2 ，k次方时间阶例１ 两个n阶方阵的乘法 for(i=1，i<=n; ++i) for(j=1; j<=n; ++j) { c[i][j]=0 ; for(k=1; k<=n; ++k) c[i][j]+=a[i][k]*b[k][j] ; }由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3时间复杂度为T(n)=O(n3)【立方阶】例２ {++x; s=0 ;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 。【常量阶】如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３ for(i=1; i<=n; ++i) { ++x; s+=x ; } 语句频度为：2n，其时间复杂度为：O(n) ，即为【线性阶】。例４ for(i=1; i<=n; ++i)for(j=1 ...继续阅读 (21)

有评论说我没有正面回答问题，那我就说清楚我到底回答了什么：第一：给出了复数域在数学上的严格定义，从而解释了“为什么把－1的平方根加进实数是一个可行的操作”；第二：解释了“为什么不能把1/0加进实数”，因为这样做会破坏实数的代数结构。你老师没讲清楚。复数相比实数并不单纯是加了个i这么简单，你还得说明加了这个i之后和原有的代数系统是相容的。如果学过抽象代数的话，那复数域可以定义成：R[x]/(x^2+1), 实系数多项式环模掉x^2+1生成的理想。因为x^2+1在实数域上不可约，所以这样模出来是个域，我们把这个域叫做复数域。然后在一般的写法中我们实际上是把多项式环里的x写成了i，然后因为模掉的理想是x^2+1,所以i^2+1=0.题主可以思考一下：有没有必要给i继续开平方，然后把开出来的新元素加到复数域里面，继续扩大数域？答案是没有必要。因为存在一个复数，其平方为i.题主可以想想这个复数具体是多少。很多高中生对这个问题都不能正确理解，总以为对i继续开方会得到复数以外的数。其实不是这样。任何一个复数开任何整数次方，得到的还是一个复数。（针对评论补充一句，我并没有说开方是一个一一映射，我的意思是存在一个复数，其n次方为原来的复数，并没有说“唯一”）这是由复数的代数闭的性质保证的（但是这并不是代数闭的定义。代数闭是指任意非常数复系数多项式的根仍然是复数，比能开方的性质更强）。实数不是代数闭的 ...继续阅读 (61)

最近用到这个技巧实在很巧妙，记录一下留在这里……数值计算中我们有时候要用一些截断的函数展开来逼近某些复杂的函数，如：这个展开的函数有可能是某些特殊函数，比如Bessel函数、Chebyshev多项式、Laguerre多项式之类的。为了计算这个函数在某个点的取值，一般的思路是把每一项的特殊函数值算出来，再乘以系数加起来。但其实这往往不是一个好主意，这样做往往是数值不稳定的，你可能会不断地用超过计算机表示范围的大数乘小数，或者用大数加小数，结果可能误差很大或者干脆发散掉。一个更好的解决方案就是Clenshaw求和。如果我们采用的特殊函数有一个递推关系：而且这个关系对于都适用（超出的项约定等于0），那么我们考虑这样一个数列：那么你会发现，算到最后，正是你要求的函数值，而对于很多特殊函数，0阶函数往往特别简单（比如Laguerre多项式，）。于是计算就完成了。为什么这是对的？解出，带入第一个式子，我们有：根据递推关系，前面的所有项都统统为0，所以。这也提示了如果递推关系不到该怎么办（比如，广义超几何函数的递推关系只在时成立）。这时候你只需要找到上式后面几项，令系数等于0解出新的递推关系补足这几个系数（注意系数可以是的函数）就好。这个算法有个特别的好处：很多时候你甚至不需要调用额外的库和函数来计算任何一个特殊函数，时间复杂度是，额外的空间开销是，比直接求和既快又省还稳定。来源：知乎 www. ...继续阅读 (27)

#The Schwartz-Zippel Algorithm##Problem: Testing Polynomial Identities判断两个多项式\(P(x_0, x_1, …, x_n),Q(x_0, x_1, …, x_n)\)在有限取值空间里是不是等价的.##Solution: A Monte Carlo algorithm随机取值测试,看看P,Q是不是一样.##Analysis and Proofd是P,Q中多项式最大的度,S是取值空间,如果P,Q不一致,而随机测试碰巧相等的概率是:d/|S|.如果自变量只有一个证明比较简单,\(H(x) = P(x) – Q(x) = w_n * x^n + … + w_0\).那么H(x)最多有n个解,取值空间大小是|S|,碰巧的可能是n/|S|.如果有多个变量的证明也是类似的.归纳法证明. ...继续阅读 (14)

考虑到存储编码中，矩阵等之间的运算都是在伽罗华域(Galois Field，GF，有限域)上进行的，所以要实现底层的运算库，必须了解 GF 上的运算规则。开始前，我们将字长设为 $w$ bit。GF 上的加法和减法运算比较简单，都是两个数值直接异或( XOR )。对乘法和除法运算，很多人可能会想到，首先按照十进制进行乘除运算，然后再将结果模上 $2^w$ 即可。这样做我们容易得到，GF 上的数值都是成对出现的，但是当 GF($n$) 中的 $n$ 不是质数时，不能构成 pairs，另外对类似于 $(3/2) \% 4$ 的运算时没有定义的，综合上面所论述的，所以 GF($2^w$) 上的乘除法运算不能简单做如上定义。GF($2^w$) 的乘除法运算规则使用到了线性代数中用最小多项式简化高次矩阵运算的理论，简单说来就是“除法原理”。我们定义 GF($2^w$) 上关于 $x$ 的多项式，即若 $r(x) = x + 1, s(x) = x$，则有 $$r(x) + s(x) = x + x + 1 = (1 + 1)x + 1 = 1$$根据“除法原理”，有 $r(x) = q(x)t(x) + s(x)$，即 $r(x) \% q(x) = s(x)$ ($q(x)$ 除 $r(x)$ 的商是$t(x)$，余数是$s(x)$)，同时， ...继续阅读 (33)

最近没有怎么更新博客，因为一直比较忙。最近发现所里在做的一个项目中，可以抽出一部分内容和0-1背包问题、子集合加总问题非常相似（虽然表面上不容易看出相似点），所以看了一些这方面的资料和论文，这里主要对问题特点和算法思想做一些整理。这类问题其实很有意思，做数学和做计算机的人都会研究，而且我这里将要提到的论文都是做计算机的人所写的。问题简述0-1 Knapsack Problem （0-1背包问题，下面简称KP）和Subset Sum Problem （子集合加总问题，下面简称SSP）是经典的NP完全问题。两个问题简要描述如下：KP：有$n$个物品要放入背包，第$i$个物品的价值为$c_i$，占据体积为$v_i$，背包的总容积为$V$，要选择一部分物品放入背包，使得他们的总价值最大。对应的优化问题是$\max_{x_i} \sum c_i * x_i $$\mbox{s.t.} \sum v_i * x_i \le V, x_i \in \{ 0, 1 \} $这里$x_i$代表是否选取第$i$个物品进背包，等于$1$就代表放入背包，等于$0$代表不放入背包。SSP: 给一个集合$\{c_1, c_2, \ldots, c_n \}$，还有一个目标值$V$，问能否选出一个子集，使得子集中元素求和刚好等于$V$。我们一般考虑的是他的另一种表述方式：选出一个子集，使得子集中元素求和不超过$ ...继续阅读 (35)

...继续阅读 (45)

继续前两篇博文中对于最小角回归（LARS)和lasso的介绍。在这篇文章中，我打算介绍一下分组最小角回归算法（Group LARS）。本文的主要观点均来自Ming Yuan和Yi Lin二人2006合作发表在JRSSB上的论文Model selection and estimation in regression with grouped variables.首先，我想说明一下，为何要引入分组变量（grouped variable)的概念。举一个简单的例子，在可加的多项式模型中，每一项都是多项式。这个多项式有可能可以通过最初的变量的线性组合来表达。在进行这种类型的回归中，挑选重要的变量其实质是挑选重要的因子（factor），而因子则是最初的那些变量的线性组合。分组变量的回归问题，实际上就是我们一般所说的回归问题的推广。如果我们把每一个单独的变量都看成一个因子，那么这种情况下的回归就是一般意义下的回归。下面用公式更加直白的说明这个问题：$$ Y=\sum_{j=1}^JX_j\beta_j+e $$其中$Y$是个$n$维向量，$e~N_n(0,\sigma^2I)$.$X_j$是$n\times p_j$矩阵，代表的是第j个因子（factor，是变量variables的线性组合)。$\beta_j$是$p_j$维的系数向量。依然假定$Y$是中心化的，$X_j$是中心化并且正交化的（$ ...继续阅读 (10)